#define _CRT_SECURE_NO_WARNINGS
//#include<bits/stdc++.h>
//using namespace std;
//int sum[2000010];
//int arr[2000010];
//int arr_copy[2000010];
//int A, B, C;
//int op[1000010][7];
//int change(int i, int j, int k) {
//    return i * (B * C) + j * C + k;
//}
//void sub(int x1, int x2, int y1, int y2, int z1, int z2, int c)
//{
//    arr[change(x1, y1, z1)] += c;
//    arr[change(x1, y1, z2 + 1)] -= c;
//    arr[change(x1, y2 + 1, z1)] -= c;
//    arr[change(x1, y2 + 1, z2 + 1)] += c;
//    arr[change(x2 + 1, y1, z1)] -= c;
//    arr[change(x2 + 1, y1, z2 + 1)] += c;
//    arr[change(x2 + 1, y2 + 1, z1)] += c;
//    arr[change(x2 + 1, y2 + 1, z2 + 1)] -= c;
//}
//void add(int x, int y, int z)
//{
//    arr[change(x, y, z)] = arr[change(x, y, z)] + arr[change(x, y - 1, z)] + arr[change(x, y, z - 1)] + arr[change(x - 1, y, z)] - arr[change(x, y - 1, z - 1)] - arr[change(x - 1, y, z - 1)] - arr[change(x - 1, y - 1, z)] + arr[change(x - 1, y - 1, z - 1)];
//}
//bool is(int num)
//{
//    memcpy(arr_copy, arr, sizeof arr);
//    for (int i = 1; i <= num; i++)
//        sub(op[i][0], op[i][1], op[i][2], op[i][3], op[i][4], op[i][5], -op[i][6]);
//    for (int i = 1; i <= A; i++)for (int j = 1; j <= B; j++)for (int k = 1; k <= C; k++)
//    {
//        add(i, j, k);
//        if (arr[change(i, j, k)] < 0)
//        {
//            memcpy(arr, arr_copy, sizeof arr);
//            return true;
//        }
//    }
//    memcpy(arr, arr_copy, sizeof arr);
//    return false;
//}
////void chafen(int x, int y, int z)
////{
////    int i = 0;
////    arr[change(x, y, z)] = arr[i = change(x, y, z)] - arr[i = change(x, y, z - 1)] - arr[i = change(x, y - 1, z)]
////        + arr[i = change(x, y - 1, z - 1)] - arr[i = change(x - 1, y, z - 1)] +
////        arr[i = change(x - 1, y, z - 1)] + arr[i = change(x - 1, y - 1, z)] - arr[i = change(x - 1, y - 1, z - 1)];
////}
//void chafen(int x, int y, int z)
//{
//    int i = 0;
//    arr[change(x, y, z)] = sum[change(x, y, z)];
//    arr[change(x, y, z)] -= sum[change(x, y, z - 1)];
//    arr[change(x, y, z)] -= sum[change(x, y - 1, z)];
//    arr[change(x, y, z)] += sum[change(x, y - 1, z - 1)];
//    arr[change(x, y, z)] -= sum[change(x - 1, y, z)];
//    arr[change(x, y, z)] += sum[change(x - 1, y, z - 1)];
//    arr[change(x, y, z)] += sum[i = change(x - 1, y - 1, z)];
//    arr[change(x, y, z)] -= sum[i = change(x - 1, y - 1, z - 1)];
//}
//int main()
//{
//    int m;
//    cin >> A >> B >> C >> m;
//    for (int i = 1; i <= A; i++)for (int j = 1; j <= B; j++)for (int k = 1; k <= C; k++)
//        cin >> sum[change(i, j, k)];
//    for (int i = 1; i <= A; i++)for (int j = 1; j <= B; j++)for (int k = 1; k <= C; k++)
//        chafen(i, j, k);
//    for (int i = 1; i <= m; i++)cin >> op[i][0] >> op[i][1] >> op[i][2] >> op[i][3] >> op[i][4] >> op[i][5] >> op[i][6];
//    int l = 1, r = m;
//    while (l < r)
//    {
//        int mid = l + r >> 1;
//        if (is(mid))
//            r = mid;
//        else
//            l = mid + 1;
//    }
//    cout << l;
//}
//#include <cstdio>
//#include <cstring>
//#include <iostream>
//#include <algorithm>
//
//using namespace std;
//
//typedef long long LL;
//
//const int N = 2000010;
//
//int A, B, C, m;
//LL s[N], b[N], bp[N];
//int d[8][4] = {
//    {0, 0, 0, 1},
//    {0, 0, 1, -1},
//    {0, 1, 0, -1},
//    {0, 1, 1, 1},
//    {1, 0, 0, -1},
//    {1, 0, 1, 1},
//    {1, 1, 0, 1},
//    {1, 1, 1, -1},
//};
//int op[N / 2][7];
//
//
//int get(int i, int j, int k)
//{
//    return (i * B + j) * C + k;
//}
//
//bool check(int mid)
//{
//    memcpy(b, bp, sizeof b);
//    for (int i = 1; i <= mid; i++)
//    {
//        int x1 = op[i][0], x2 = op[i][1], y1 = op[i][2], y2 = op[i][3], z1 = op[i][4], z2 = op[i][5], h = op[i][6];
//        b[get(x1, y1, z1)] -= h;
//        b[get(x1, y1, z2 + 1)] += h;
//        b[get(x1, y2 + 1, z1)] += h;
//        b[get(x1, y2 + 1, z2 + 1)] -= h;
//        b[get(x2 + 1, y1, z1)] += h;
//        b[get(x2 + 1, y1, z2 + 1)] -= h;
//        b[get(x2 + 1, y2 + 1, z1)] -= h;
//        b[get(x2 + 1, y2 + 1, z2 + 1)] += h;
//    }
//
//    memset(s, 0, sizeof s);
//    for (int i = 1; i <= A; i++)
//        for (int j = 1; j <= B; j++)
//            for (int k = 1; k <= C; k++)
//            {
//                s[get(i, j, k)] = b[get(i, j, k)];
//                for (int u = 1; u < 8; u++)
//                {
//                    int x = i - d[u][0], y = j - d[u][1], z = k - d[u][2], t = d[u][3];
//                    s[get(i, j, k)] -= s[get(x, y, z)] * t;
//                }
//
//                if (s[get(i, j, k)] < 0) return true;
//            }
//
//    return false;
//}
//
//int main()
//{
//    scanf("%d%d%d%d", &A, &B, &C, &m);
//
//    for (int i = 1; i <= A; i++)
//        for (int j = 1; j <= B; j++)
//            for (int k = 1; k <= C; k++)
//                scanf("%lld", &s[get(i, j, k)]);
//
//    for (int i = 1; i <= A; i++)
//        for (int j = 1; j <= B; j++)
//            for (int k = 1; k <= C; k++)
//                for (int u = 0; u < 8; u++)
//                {
//                    int x = i - d[u][0], y = j - d[u][1], z = k - d[u][2], t = d[u][3];
//                    bp[get(i, j, k)] += s[get(x, y, z)] * t;
//                }
//
//    for (int i = 1; i <= m; i++)
//        for (int j = 0; j < 7; j++)
//            scanf("%d", &op[i][j]);
//
//    int l = 1, r = m;
//    while (l < r)
//    {
//        int mid = l + r >> 1;
//        if (check(mid)) r = mid;
//        else l = mid + 1;
//    }
//
//    printf("%d\n", r);
//
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//int arr[200010];
//int main()
//{
//    int n;
//    cin >> n;
//    while (n--)
//    {
//        int N;
//        cin >> N;
//        if (N == 1)
//        {
//            cout << 1 << endl;
//            continue;
//        }
//        if (N % 2 == 0) {
//            cout << -1 << endl;
//        }
//        else {
//           
//            int j = 3;
//            arr[N - 1] = N; arr[N] = 2;
//            for (int i = 1; i < N - 1; i++, j++)
//            {
//                arr[i] = i + j;
//                arr[i] %= N;
//                if (arr[i] == 0)arr[i] = N;
//            }
//            for (int i = 1; i <= N; i++)
//                cout << arr[i] << ' ';
//            cout << endl;
//        }
//    }
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//
//LL n, m, k;
//bool check(LL mid)
//{
//    LL a = (m + 1) / (mid + 1);
//    LL b = m-a*(mid+1)+1;
//    if (b)b--;
//    if ((a * mid + b) * n >= k)return true;
//    return false;
//}
//int main()
//{
//    int t;
//    cin >> t;
//    while (t--) {
//        cin >> n >> m >> k;
//        if (k <= n)cout << 1 << endl;
//        else {
//            int l = 1, r = m;
//            while (l < r)
//            {
//                int mid = l + r >> 1;
//                if (check(mid))
//                {
//                    r = mid;
//                }
//                else
//                    l = mid + 1;
//            }
//            cout << l << endl;
//        }
//    }
//}
//#include<bits/stdc++.h>
//using namespace std;
//char arr[60][60];
//int main()
//{
//    int t;
//    cin >> t;
//    while (t--)
//    {
//        int n, m;
//        cin >> n >> m;
//        for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> arr[i][j];
//        int flag = 1;
//        for (int i = 2; i <= n; i++)for (int j = 2; j <= m; j++)
//            if (arr[i][j] == '1' && ('0' == arr[i - 1][j] && '0' == arr[i][j - 1]))
//                flag = 0;
//        if (flag)
//            cout << "YES" << endl;
//        else
//            cout << "NO" << endl;
//    }
//}
//#include<bits/stdc++.h>
//using namespace std;
//char arr[60][60];
//bool check(int x, int y)
//{
//    int flag = 1;
//    for (int i = 1; i <= x; i++)if (arr[i][y] == '0')flag = 0;
//    if (flag)return true;
//    for (int j = 1; j <= y; j++)if (arr[x][j] == '0')return 0;
//    return true;
//}
//int main()
//{
//    int t;
//    cin >> t;
//    while (t--)
//    {
//        int n, m;
//        cin >> n >> m;
//        for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> arr[i][j];
//        int flag = 1;
//        for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)
//        {
//            if (arr[i][j] == '1' && check(i, j) == 0) {
//                flag = 0;
//                break;
//            }
//            if (flag == 0)break;
//        }
//        if (flag)
//            cout << "YES" << endl;
//        else
//            cout << "NO" << endl;
//    }
//}
//#include<bits/stdc++.h>
//using namespace std;
//char arr[60][60];
//bool check(int x, int y)
//{
//    int flag = 1;
//    for (int i = 1; i <= x; i++)if (arr[i][y] == '0')flag = 0;
//    if (flag)return true;
//    for (int  j = 1; j <= y; j++)if (arr[x][j] == '0')return 0;
//    return true;
//}
//int main()
//{
//    int t;
//    cin >> t;
//    while (t--)
//    {
//        int n, m;
//        cin >> n >> m;
//        for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> arr[i][j];
//        int flag = 1;
//        for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)
//        {
//            if (arr[i][j] == '1' && check(i, j) == 0) {
//                flag = 0;
//                break;
//            }
//            if (flag == 0)break;
//        }
//        if (flag)
//            cout << "YES" << endl;
//        else
//            cout << "NO" << endl;
//    }
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//LL sum1[1010][1010];
//LL arr[100010];
//LL Sum[100010];
//int main()
//{
//    int n;
//    cin >> n;
//    memset(sum1, 0x3f3f3f3f, sizeof sum1);
//    for (int i = 1; i <= n; i++)sum1[i][i] = 0;
//    for (int i = 1; i <= n; i++) {
//        cin >> arr[i]; Sum[i] = Sum[i - 1] + arr[i];
//    }
//    for (int len = 2; len <= n; len++)
//    {
//        for (int i = 1; i + len - 1 <= n; i++) {
//            int j = i + len - 1;
//            for (int k = i; k < j; k++)
//                sum1[i][j] = min(sum1[i][j], sum1[i][k] + sum1[k + 1][j] + (Sum[j] - Sum[k]) * (Sum[k] - Sum[i - 1]));
//        }
//    }
//    cout << sum1[1][n];
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//const int N = 1e5 + 10;
//LL arr[N];
//int main()
//{
//    int n, k=0, m;
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++)cin >> arr[i];
//    sort(arr + 1, arr + n + 1);
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= n; j++)
//        {
//            if (i == j)continue;
//            string ans = to_string(arr[i]) + to_string(arr[j]);
//            LL an = stoll(ans);
//            if (an % m == 0)k++;
//        }
//    cout << k;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//LL arr[10010];
//LL brr[10010];
//int fa(int a)
//{
//    if (a == arr[a])
//        return a;
//    return arr[a] = fa(arr[a]);
//}
//typedef  pair<LL, LL> PLL;
//PLL crr[100010];
//int main()
//{
//    int n, m;
//    cin >> n >> m;
//    int num = 0;
//    for (int i = 1; i <= n; i++)
//        arr[i] = i;
//    for (int i = 1; i <= m; i++)
//    {
//        int a, b, c;
//        cin >> a >> b >> c;
//        if (a == 1) {
//            int f1 = fa(a);
//            int f2 = fa(b);
//            arr[f1] = f2;
//        }
//        else
//        {
//            crr[num++] = make_pair(b, c);
//        }
//    }
//    for (int i = 0; i < num; i++)
//    {
//        brr[fa(crr[i].first)] +=
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        cout << brr[fa(i)] << ' ';
//    }
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//LL arr[10010];
//LL brr[10010];
//int fa(int a)
//{
//    if (a == arr[a])
//        return a;
//    return arr[a] = fa(arr[a]);
//}
//typedef  pair<LL, LL> PLL;
//PLL crr[100010];
//int main()
//{
//    int n, m;
//    cin >> n >> m;
//    int num = 0;
//    for (int i = 1; i <= n; i++)
//        arr[i] = i;
//    for (int i = 1; i <= m; i++)
//    {
//        int a, b, c;
//        cin >> a >> b >> c;
//        if (a == 1) {
//            int f1 = fa(b);
//            int f2 = fa(c);
//            arr[f1] = f2;
//        }
//        else
//        {
//            brr[fa(b)] += c;
//        }
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        cout << brr[fa(i)] << ' ';
//    }
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//const int N = 1e5 + 10;
//LL mp[11][N];
//LL arr[N];
//LL ha[11] = { 1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000 };
//int main()
//{
//    int n, k = 0, m;
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++)cin >> arr[i];
//    for (int i = 1; i < 11; i++)
//    {
//        for (int j = 1; j <= n; j++)
//        {
//            LL mod = (arr[i] % m * ha[i] % m)%m;
//            mp[i][mod]++;
//        }
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        int mod = arr[i] % m;
//        int num = 0;
//        LL x = arr[i];
//        while (arr[i])
//        {
//            arr[i] /= 10;
//            num++;
//        }
//        k += mp[num][(m - mod)%m];
//        if (((x%m * ha[num]%m+x) %m)== 0)k--;
//    }
//    cout << k;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//LL Max = -1, Min = 0x3f3f3f3f;
//double sum = 0;
//int main()
//{
//    cout << sum << endl;
//    int n;
//    cin >> n;
//    while (n--)
//    {
//        LL x;
//        cin >> x;
//        Max = max(Max, x);
//        Min = min(Min, x);
//        sum += x;
//    }
//    sum /= n;
//    cout << Max << endl << Min << endl << sum;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//LL Max = -1, Min = 0x3f3f3f3f;
//double sum = 0;
//int main()
//{
//    cout << sum << endl;
//    int n;
//    cin >> n;
//    while (n--)
//    {
//        LL x;
//        cin >> x;
//        Max = max(Max, x);
//        Min = min(Min, x);
//        sum += x;
//    }
//    sum /= n;
//    cout << Max << endl << Min << endl << sum;
//}
//#include<bits/stdc++.h>
//using namespace std;
//
//typedef long long LL;
//const int N = 100000;
//LL l[N], r[N];
//int v[26];
//int main()
//{
//    string s;
//    cin >> s;
//    s = " " + s;
//    for (int i = 0; i < 26; i++)v[i] = 0;
//    for (int i = 1; i < s.size(); i++)
//    {
//        l[i] = v[s[i] - 'a'];
//        v[s[i] - 'a'] = i;
//    }
//    for (int i = 0; i < 26; i++)v[i] = s.size();
//    for (int i = s.size() - 1; i; i--)
//    {
//        r[i] = v[s[i] - 'a'];
//        v[s[i] - 'a'] = i;
//    }
//    LL sum = 0;
//    for (LL i = 1; i < s.size(); i++)
//        sum += (i - l[i]) * (r[i] - i);
//    cout << sum;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//int v[26];
//int l[100010];
//int main()
//{
//    string s;
//    cin >> s;
//    int n = s.size();
//    s = " " + s;
//    for (int i = 1; i <= n; i++)
//    {
//        l[i] = v[s[i] - 'a'];
//        v[s[i] - 'a'] = i;
//    }
//    LL sum = 0;
//    LL ans = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        ans = ans + (i - l[i]);
//        sum += ans;
//    }
//    cout << sum;
//}
//#include<bits/stdc++.h>
//using namespace std;
//class Solution {
//public:
//    int arr[210][210] = { 0 };
//    int getMoneyAmount(int n) {
//        return getMax(1, n);
//    }
//    int getMax(int l, int r) {
//        if (l >= r)return 0;
//        if (arr[l][r])return arr[l][r];
//        int Max = 0x3f3f3f3f;
//        for (int i = l; i <= r; i++)
//            Max = min(Max, max(getMax(l, i - 1) , (i + 1, r)) + i);
//        return arr[l][r] = Max;
//    }
//};
//#include<bits/stdc++.h>
//using namespace std;
//int arr[110][110];
//int ele[110][110];
//int main()
//{
//    int n;
//    cin >> n;
//    memset(arr, -1, sizeof arr);
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= i; j++)cin >> ele[i][j];
//    for (int i = 2; i <= n; i++)
//        for (int j = 1; j <= i; j++)
//        {
//            int x = ele[i][j];
//            if (abs(i-1-j-j) > 1) {
//                continue;
//            }
//                if (abs(i - 2-j - j) > 1)continue;
//                ele[i][j] = x + ele[i - 1][j];
//                if(abs(i-2-2*(j-1))>1)
//                ele[i][j] = max(ele[i][j], x + ele[i-1][j - 1]);
//        }
//    int Max = 0;
//    for (int i = 1; i <= n; i++)
//        if (abs(n-1-i-i) <= 1)
//            Max = max(ele[n][i], Max);
//    cout << Max;
//}
//#include<iostream>
//#include<cstring>
//#include<cstdio>
//#include<algorithm>
//using namespace std;
//const int N = 110;
//int n;
//
//int f[N][N];
//int triangle[N][N];
//int main()
//{
//    scanf("%d", &n);
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= i; j++)
//            scanf("%d", &triangle[i][j]);
//
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= i; j++)
//            f[i][j] = max(f[i - 1][j], f[i - 1][j - 1]) + triangle[i][j];
//    if (n % 2 == 0) printf("%d\n", max(f[n][n / 2], f[n][n / 2 + 1]));
//    else printf("%d\n", f[n][n / 2 + 1]);
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//int arr[110][110];
//int ele[110][110];
//int main()
//{
//    int n;
//    cin >> n;
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= i; j++)cin >> ele[i][j];
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= i; j++)
//            ele[i][j] += max(ele[i - 1][j], ele[i - 1][j - 1]);
//
//    if (n % 2)
//        cout << max(ele[n][n / 2 + 1], ele[n][n / 2]);
//    else
//        cout << ele[n][(1 + n) / 2];
//}
//#include<bits/stdc++.h>
//using namespace std;
//int e[2010], ne[2010], h[2010], g[2010], w[2010];
//int t[2010];
//int dis[2010];
//bool is[2010];
//int N, M, K, T;
//typedef pair<int, int> PII;
//int idx;
//void add(int a, int b, int c)
//{
//    e[idx] = c, ne[idx] = h[a], h[a] = idx, g[idx] = b, w[idx++] = max(t[a], t[b]);
//}
//void diji()
//{
//    priority_queue<PII, vector<PII>, greater<PII>>pq;
//    for (int i = 1; i <= N; i++)
//    {
//        if (dis[i])continue;
//        pq.push({ dis[i],i });
//    }
//    while (pq.size())
//    {
//        auto it = pq.top();
//        pq.pop();
//
//        int x = it.first;
//        int y = it.second;
//        if (is[y])continue;
//        is[y] = true;
//        for (int i = h[y]; i != -1; i = ne[i])
//        {
//            int j = e[i];
//            //if(is[j])continue;
//            if (dis[j] > max(dis[y], dis[g[i]]) + w[i])
//            {
//                dis[j] = max(dis[y], dis[g[i]]) + w[i];
//                pq.push({ dis[j],j });
//            }
//        }
//    }
//}
//int main() {
//    memset(h, -1, sizeof h);
//    memset(dis, 0x3f, sizeof dis);
//    cin >> N >> M >> K >> T;
//    for (int i = 1; i <= N; i++)cin >> t[i];
//    for (int i = 1; i <= M; i++) {
//        int x;
//        cin >> x; dis[x] = 0;
//    }
//    for (int i = 1; i <= K; i++) {
//        int a, b, c;
//        cin >> a >> b >> c;
//        add(a, b, c);
//        add(b, a, c);
//    }
//    diji();
//    cout << dis[T];
//}
//#include<bits/stdc++.h>
//using namespace std;
//bool dp[100][100010];
//int main()
//{
//    int n;
//    cin >> n;
//    dp[0][0] = true;
//    int sum = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        int x;
//        cin >> x;
//        /*
//        if ��ѡ
//        dp[i][j]=dp[i-1][j]
//        elif ���ұ�
//        dp[i][j]=dp[i-1][j-x]
//        else
//        dp[i][j]=dp[i-1][j+x]
//[        */
//        for (int j = 0; j<=100000; j++)
//        {
//            dp[i][j] = dp[i - 1][j];
//            dp[i][j] = max(dp[i][j], dp[i-1][abs(j - x)]);
//            dp[i][j]= max(dp[i][j], dp[i-1][x+j]);
//            
//        }
//    }
//    for(int i=1;i<=100000;i++)
//        if (dp[n][i])sum++;
//    cout << sum;
//}
//#include<bits/stdc++.h>
//using namespace std;
//bool dp[100][100010]; 
//int main()
//{
//    int n;
//    cin >> n;
//    dp[0][0] = true;
//    int sum = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        int x;
//        cin >> x;
//        /*
//        if ��ѡ
//        dp[i][j]=dp[i-1][j]
//        elif ���ұ�
//        dp[i][j]=dp[i-1][j-x]
//        else
//        dp[i][j]=dp[i-1][j+x]
//[        */
//        for (int j = 0; j <= 100000; j++)
//        {
//            dp[i][j] = dp[i - 1][j];
//            dp[i][j] = max(dp[i][j], dp[i - 1][abs(j - x)]);
//            if(x+j<=100000)
//            dp[i][j] = max(dp[i][j], dp[i - 1][x + j]);
//
//        }
//    }
//    for (int i = 1; i <= 100000; i++)
//        if (dp[n][i])
//            sum++;
//    cout << sum;
//}
//#include<bits/stdc++.h>
//using namespace std;
//const int N = 1e5 + 10;
//int e[N], ne[N], h[N];
//int idx;
//void add(int a, int b)
//{
//    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
//}
//int dfs(int root)
//{
//    int sum = 0;
//    int Max = 0;
//    for (int i = h[root]; ~i; i = ne[i])
//    {
//        int j = e[i];
//        sum++;
//        Max = max(Max, dfs(j));
//    }
//    if (Max + sum)return Max + sum;
//    return 1;
//}
//int main()
//{
//    memset(h, -1, sizeof h);
//    int n;
//    cin >> n;
//    for (int i = 2; i <= n; i++)
//    {
//        int j;
//        cin >> j;
//        add(j, i);
//    }
//    cout << dfs(1)-1;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//LL arr[200010];
//struct dat {
//    LL a, b, c;
//    bool operator<(const dat d)const
//    {
//        return a > d.a;
//    }
//};
//priority_queue<dat, vector<dat>>pq;
//int main()
//{
//    LL N, M;
//    cin >> N >> M;
//    for (int i = 1; i <= N; i++)
//        cin >> arr[i];
//    for (int i = 1; i <= M; i++)
//    {
//
//        LL a, b, c, d;
//        cin >> a >> b >> c >> d;
//        while (pq.size())
//        {
//            if (pq.top().a <= a)
//            {
//                auto it = pq.top();
//                pq.pop();
//                arr[it.b] += it.c;
//            }
//            else
//                break;
//        }
//        if (arr[b] >= d)
//        {
//            cout << arr[b] - d << endl;
//            pq.push({ a + c,b,d });
//            arr[b] -= d;
//        }
//        else
//            cout << -1 << endl;
//    }
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//LL MOD = 1000000007;
//int M = 1 << 6;
//LL dp[110][M][M][30];
//int lowbit(int x) {
//    return x & -x;
//}
//int cnt(int x)
//{
//    int sum = 0;
//    for (x; x; x -= lowbit(x))
//        sum++;
//    return sum;
//}
//int main()
//{
//    LL n, m, k;
//    cin >> n >> m >> k;
//    f[0][0][0][0] = 1;
//    for (int i = 1; i <= m; i++)
//        for (int a = 0; a < 1 << n; a++)
//        {
//            for (int b = 0; b < 1 << n; b++)
//            {
//                if (a & (b >> 2) || (a >> 2) & b)continue;
//                for (int c = 0; c < 1 << n; c++)
//                {
//                    if ((b >> 2) & c || (c >> 2) & b)continue;
//                    if ((a >> 1) & b || (b >> 1) & a)continue;
//                    for (int j = cnt(a); j <= k; j++)
//                    {
//                        dp[i][a][b][j] += dp[i][b][c][j - cnt(a)];
//                        dp[i][a][b][j] %= MOD;
//                    }
//                }
//            }
//        }
//    LL ans = 0;
//    for (int i = 0; i < 1 << n; i++)
//        for (int j = 0; j < 1 << n; j++)
//            ans = (ans + dp[m][i][j][k]) % MOD; cout << ans;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//const int N = 1e5 + 10;
//LL arr[N];
//LL brr[N];
//int n, m;
//bool check(int mid)
//{
//    memcpy(brr, arr, sizeof arr);
//    for (int i = 1; i < n; i++)
//    {
//        int I = i;
//        for (int j = i; j <= I + mid - 1 && j <= n; j++)
//            if (brr[j]>=m)i = j;
//        if (i == I)return 0;
//        brr[i] -= m;
//    }
//    for (int i = 1; i < n; i++)
//    {
//        int I = i;
//        for (int j = i; j<=n&&j <= I + mid - 1; j++)
//            if (brr[j]>=m)i = j;
//        if (i == I)return 0;
//        brr[i] -= m;
//    }
//    return true;
//}
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i < n; i++)
//        cin >> arr[i];
//    arr[n] = 2 * m;
//    int l = 1, r = n;
//    while (l < r)
//    {
//        int mid = l + r >> 1;
//        if (check(mid))r = mid;
//        else
//            l = mid + 1;
//    }
//    cout << l << endl;
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//const int N = 1e5 + 10;
//LL arr[N];
//int n, m;
//bool check(int mid)
//{
//    LL sum = 0;
//    for (int i = 1, j = 1; j < n; j++)
//    {
//        sum += arr[j];
//        if (j - i + 1 > mid)
//            sum -= arr[i++];
//        if (sum < 2 * m)return 0;
//    }
//    return 1;
//}
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i < n; i++)
//        cin >> arr[i];
//    int l = 1, r = n;
//    while (l < r)
//    {
//        int mid = l + r >> 1;
//        if (check(mid))r = mid;
//        else
//            l = mid + 1;
//    }
//    cout << l << endl;
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//LL dp[5010][5010];
//int main()
//{
//    string s;
//    cin >> s;
//    int n = s.size();
//    s = " " + s;
//    int ans = 0;
//    for (int len = 2; len <= n; len++)
//    {
//        for (int i = 1; i + len - 1 <= n; i++)
//        {
//            int j = i + len - 1;
//            if (s[i] < s[j]);
//            else if (s[i] == s[j])
//                dp[i][j] = dp[i + 1][j - 1];
//            else dp[i][j] = 1;
//            ans += dp[i][j];
//        }
//    }
//    cout << ans;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//LL arr[40];
//int n;
//LL m;
//LL ans = 50;
//LL sum[50];
//unordered_map<LL, LL>mp;
//void dfs(int pos, LL weight, LL knife)
//{
//    if (weight > m)return;
//    if (pos > n/2)
//    {
//        if (mp.count(weight)==0)
//            mp[weight] = knife;
//        else
//            mp[weight] = min(knife, mp[weight]);
//        return;
//    }
//    dfs(pos + 1, weight, knife);
//    dfs(pos + 1, weight + arr[pos], knife);
//    dfs(pos + 1, weight + arr[pos] / 2, knife + 1);
//}
//void dfs_(int pos, LL w, LL k)
//{
//    if (w > m)return;
//    if (k >= ans)return;
//    if (pos > n) {
//        if (mp.count(m - w))
//            ans = min(ans, mp[m - w] + k);
//        return;
//    }
//    dfs_(pos + 1, w, k);
//    dfs_(pos + 1, w + arr[pos], k);
//    dfs_(pos + 1, w + arr[pos] / 2, k + 1);
//}
//int main()
//{
//    cin >> n >> m;
//    m *= 2;
//    for (int i = 1; i <= n; i++)cin >> arr[i], arr[i] *= 2, sum[i] = sum[i - 1] + arr[i];
//    sort(arr + 1, arr + n + 1, greater<LL>());
//    dfs(1, 0, 0);
//    dfs_(n / 2 + 1, 0, 0);
//    if (ans == 50)cout << -1;
//    else
//        cout << ans;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//const int N = 2e5 + 10;
//int e1[2 * N], ne1[2 * N], h1[N];
//int e2[N * 2], ne2[N * 2], h2[N];
//int idx1, idx2;
//int n, m;
//int w1[N], w2[N];
//void add1(int a, int b)
//{
//    e1[idx1] = b, ne1[idx1] = h1[a], h1[a] = idx1++;
//}
//void add2(int a, int b)
//{
//    e2[idx2] = b, ne2[idx2] = h2[a], h2[a] = idx2++;
//}
//int dfs(int r1, int f1, int r2, int f2)
//{
//    int flag = 0;
//    int Max = 0;
//    if (w1[r1] == w2[r2])
//    {
//        flag = 1;
//        for (int i = h1[r1]; ~i; i = ne1[i])
//        {
//            if (e1[i] == f1)continue;
//            for (int I = h2[r2]; ~I; I = ne2[I])
//            {
//                if (e2[I] == f2)continue;
//                Max = max(Max, dfs(e1[i], r1, e2[I], r2));
//            }
//        }
//    }
//    return Max + flag;
//}
//int main()
//{
//    memset(h1, -1, sizeof h1);
//    memset(h2, -1, sizeof h2);
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++)cin >> w1[i];
//    for (int i = 1; i <= n; i++)cin >> w2[i];
//    for (int i = 0; i < n - 1; i++)
//    {
//        int a, b;
//        cin >> a >> b;
//        add1(a, b);
//        add1(b, a);
//    }
//    for (int i = 0; i < m - 1; i++)
//    {
//        int a, b;
//        cin >> a >> b;
//        add2(a, b);
//        add2(b, a);
//    }
//    cout << dfs(1, -1, 1, -1);
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//LL arr[100010];
//LL brr[100010];
//LL N, K, T;
//bool check(int mid)
//{
//    memcpy(brr, arr, sizeof arr);
//    sort(brr + 1, brr + 1 + mid);
//    LL t = K * T * K;
//    LL s = 0;
//    LL S = 0;
//    for (int i = 1, j = 1; j <= mid; j++)
//    {
//        s += brr[j];
//        S += brr[j] * brr[j];
//        if (j - i + 1 > K)
//        {
//            s -= brr[i];
//            S -= brr[i] * brr[i];
//            i++;
//        }
//        if (j - i + 1 == K)
//        {
//            LL ans = S * K - s * s;
//            if (ans < t)return true;
//        }
//    }
//    return false;
//}
//int main()
//{
//    cin >> N >> K >> T;
//    for (int i = 1; i <= N; i++)
//    {
//        cin >> arr[i];
//    }
//    int l = 1, r = N;
//    // for(int i=1;i<=N;i++)
//    // {
//    //     sum[i]=sum[i-1]+arr[i]*arr[i];
//    // }
//    while (l < r)
//    {
//        int mid = l + r >> 1;
//        if (check(mid))
//            r = mid;
//        else
//            l = mid + 1;
//    }
//    if (check(l))
//        cout << l;
//    else
//        cout << -1;
//}
//#include<bits/stdc++.h>
//using namespace std;
//const int N = 4e5 + 10;
//int e[N * 2], ne[N * 2], h[N];
//int idx;
//int n, M;
//void add(int a, int b)
//{
//    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
//}
//queue<int>q;
//int depth[N];
//int fa[N][16];
//bool is[N];
//void bfs(int root)
//{
//    memset(depth, 0x3f, sizeof depth);
//    depth[0] = 0;
//    depth[root] = 1;
//    q.push(root);
//    while (q.size())
//    {
//        int x = q.front();
//        q.pop();
//        if (is[x])continue;
//        is[x] = true;
//        for (int i = h[x]; i!=-1; i = ne[i])
//        {
//            int j = e[i];
//            if (depth[j] > depth[x] + 1) {
//                depth[j] = depth[x] + 1;
//                q.push(j);
//                fa[j][0] = x;
//                for (int k = 1; k < 16; k++)
//                {
//                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
//                }
//            }
//        }
//    }
//}
//int lca(int a, int b)
//{
//    if (depth[a] < depth[b])swap(a, b);
//    for (int k = 15; k >= 0; k--)
//    {
//        if (depth[fa[a][k]] >= depth[b])
//            a = fa[a][k];
//    }
//    if (a == b)return a;
//    for (int k = 15; k >= 0; k--)
//    {
//        if (fa[a][k] != fa[b][k])
//        {
//            a = fa[a][k], b = fa[b][k];
//        }
//    }
//    return fa[a][0];
//}
//int main()
//{
//    cin >> n;
//    memset(h, -1, sizeof h);
//    int root = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        int a, b;
//        cin >> a >> b;
//        if (b == -1)root = a;
//        else
//            add(a, b), add(b, a);
//    }
//    bfs(root);
//    cin >> M;
//    while (M--)
//    {
//        int a, b;
//        cin >> a >> b;
//        int t = lca(a, b);
//        if (t == a)
//            cout << 1 << endl;
//        else if(t == b)cout << 2 << endl;
//        else
//            cout << 0 << endl;
//    }
//}
//#include<bits/stdc++.h>
//using namespace std;
//int main()
//{
//    int t;
//    cin >> t;
//    while (t--)
//    {
//        int n, k;
//        cin >> n >> k;
//        string s;
//        cin >> s;
//        int sum = 0;
//        int flag = 0;
//        for (int i = 0, j = s.size() - 1; i < j; i++, j--)
//            if (s[i] > s[j]) {
//                flag = -1; break;
//            }
//            else if (s[i] < s[j]) {
//                flag = 1; break;
//            }
//            else {
//                for (int k = i + 1; k < j; k++)
//                {
//                    if (s[k] != s[j])
//                    {
//                        flag = -1;
//                        break;
//                    }
//                    
//                }
//                break;
//            }
//        if (flag == 0)
//            cout << "NO" << endl;
//        else if (flag == 1)
//            cout << "YES" << endl;
//        else {
//            if (flag == -1 && k >= 1)cout << "YES" << endl;
//            else
//                cout << "NO" << endl;
//        }
//    }
//}
//#include<bits/stdc++.h>
//using namespace std;
//int arr[10000];
//typedef pair<int, int> PII;
//
//int main()
//{
//    int t;
//    cin >> t;
//    while (t--)
//    {
//        int n;
//        cin >> n;
//        int flag = 0;
//        vector<PII>v;
//        for (int i = 1; i <= n; i++)cin >> arr[i];
//        int i = 0;
//        for (i = n - 1; i>0; i-=2)
//        {
//            if (arr[i + 1]==0||arr[i]==0)
//            {
//                v.push_back({ i,i + 1 });
//                arr[i] = arr[i + 1] = 1;
//            }
//        }
//        if (arr[1] == 0)
//            v.push_back({ 1,2 });
//        cout << v.size() + 1 << endl;
//        for (auto i : v)cout << i.first << ' ' << i.second << endl;
//        cout << 1 << ' ' << n - v.size() << endl;
//    }
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//int main()
//{
//    int t;
//    cin >> t;
//    while (t--)
//    {
//        LL a, b;
//        cin >> a >> b;
//        if (a == b)
//        {
//            cout << -1 << endl;
//            continue;
//        }
//        int arr[80] = { 0 };
//        int brr[80] = { 0 };
//        for (int i = 0; i < 31; i++)
//            arr[i] = (a >> i) & 1;
//        for (int i = 0; i < 31; i++)
//            brr[i] = (b >> i) & 1;
//        int crr[80] = { 0 };
//        LL ans = 0;
//        for (int i = 0; i < 71; i++)
//        {
//            if (arr[i] && brr[i])
//            {
//                ans += (1 << i);
//                arr[i + 1]++;
//                brr[i + 1]++;
//                int j = i + 1;
//                while (arr[j] > 1)
//                {
//                    arr[j] = 0;
//                    arr[j + 1]++;
//                }
//                j = i + 1;
//                while (brr[j] > 1)
//                {
//                    brr[j] = 0;
//                    brr[j + 1]++;
//                }
//            }
//        }
//        cout << ans << endl;
//    }
//}
//#include<bits/stdc++.h>
//using namespace std;
//const int N = 20010;
//int a[N], b[N];
//int main()
//{
//    int n, m;
//    cin >> n >> m;
//    vector<int>v(m + 1);
//    for (int i = 0; i < n; i++)
//    {
//        int x, y, z;
//        cin >> x >> y >> z;
//        memcpy(b, a, sizeof a);
//        for (int j = 0; j < x; j++)
//        {
//            queue<int>q;
//            int hh = 0, tt = -1;
//            for (int k = j; k <= m; k += x) {
//                if (q.size()&&(k - q.front()) / x > z)q.pop();
//                if(q.size())
//                a[k] = max(a[k], b[q.front()] + (k - q.front()) / x * y);
//                while (q.size() && b[k] >= (b[q.back()] + (k - j) / x * y))  q.pop();
//                q.push(k);
//      /*    
//                    while (hh <= tt && k - c[hh] > z * x)hh++;
//                if (hh <= tt)
//                    a[k] = max(a[k], (k - c[hh]) / x * y + b[c[hh]]);
//                while (hh <= tt && b[c[tt]] - (c[tt] - j) / x * y <= b[k] - (k - j) / x * y)tt--;
//                c[++tt] = k;*/
//
//            }
//        }
//    }
//    cout << a[m];
//    return 0;
//}
//#include<iostream>
//using namespace std;
//int dp[2000][1000];
//int main()
//{
//    int n, a, b;
//    cin >> a >> b >> n;
//
//    for (int i = 1; i <= n; i++)
//    {
//        int x, y;
//        cin >> x >> y;
//        for (int j = a; j >= x; j--)
//        {
//            for (int k = b; k > y; k--)
//            {          // cout<<"66"<<endl;
//                dp[j][k] = max(dp[j][k], dp[j - x][k - y] + 1);
//            }
//        }
//    }
//    int k = b;
//    while (k && dp[a][k] == dp[a][k - 1])k--;
//    cout << dp[a][k] << ' ';
//    cout << b - k << endl;
//}
//#include<bits/stdc++.h>
//using namespace std;
//int arr[100010];
//int main()
//{
//    int t;
//    cin >> t;
//    while (t--)
//    {
//        int n;
//        cin >> n;
//        for (int i = 1; i <= n; i++)cin >> arr[i];
//        int flag = 0;
//        for (int i = 1; i < n; i++)
//        {
//            if (arr[i] + arr[i] > arr[i + 1] && arr[i + 1] * 2 > arr[i])flag = 1;
//        }
//        if (flag)cout << "YES" << endl;
//        else
//            cout << "NO" << endl;
//    }
//}
//#include<bits/stdc++.h>
//using namespace std;
//#define x first
//#define y second
//typedef pair<int, int> PII;
//PII arr[200010];
//char brr[200010];
//int main()
//{
//    int t;
//    cin >> t;
//    while (t--)
//    {
//        int n;
//        cin >> n;
//        for (int i = 1; i <= n; i++)cin >> arr[i].x >> arr[i].y;
//        sort(arr + 1, arr + 1 + n);
//        int flag = 0;
//        int l = 0;
//        for (int i = 1; i <= n; i++)
//        {
//            if (arr[i].x > l) {
//                l = arr[i].x; brr[i] = '1';
//            }
//            else if (arr[i].x <= l && arr[i].y > l) { l++; brr[i] = '1'; }
//            else { brr[i] = brr[i - 1] = '0'; }
//
//        }
//        for (int i = 1; i <= n; i++)cout << brr[i];
//        cout << endl;
//    }
//}
//#include<bits/stdc++.h>
//using namespace std;
//#define x first
//#define y second
//typedef pair<int, int> PII;
//PII arr[200010];
//int brr[200010];
//int main()
//{
//    int t;
//    cin >> t;
//    while (t--)
//    {
//        int n;
//        cin >> n;
//        for (int i = 1; i <= n; i++)cin >> arr[i].x >> arr[i].y;
//        sort(arr + 1, arr + 1 + n);
//        int flag = 0;
//        int l = 0;
//        for (int i = 1; i <= n; i++)
//        {
//            int flag = 0;
//            while (i < n && arr[i].x == arr[i + 1].x && arr[i].y == arr[i + 1].y && arr[i].x == arr[i].y)
//            {
//                brr[i] = 0;
//                i++;
//                flag = 1;
//            }
//            if (flag)
//                brr[i] = 0;
//            else
//                brr[i] = 1;
//        }
//        for (int i = 1; i <= n; i++)cout << brr[i];
//        cout << endl;
//    }
//}
//#include<bits/stdc++.h>
//using namespace std;
//const int N = 4e5 + 10;
//int sum[N];
//int num[N];
//
//int arr[N];
//int brr[N];
//void solve() {
//    int n;
//    cin >> n;
//    for (int i = 1; i <= 2 * n; i++)sum[i] = num[i] = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> arr[i] >> brr[i];
//        if (arr[i] == brr[i])
//        {
//            num[arr[i]]++;
//            sum[arr[i]] = 1;
//        }
//    }
//    for (int i = 2; i <= 2 * n; i++)sum[i] += sum[i - 1];
//    for (int i = 1; i <= n; i++)
//    {
//        if (arr[i] == brr[i]) {
//            cout << (num[arr[i]] <= 1);
//        }
//        else {
//            int x = arr[i], y = brr[i];
//            if (sum[y] - sum[x - 1] < (y - x + 1))cout << 1; else cout << 0;
//        }
//    }
//    cout << endl;
//}
//int main()
//{
//    ios::sync_with_stdio(0);
//    cin.tie(0);
//    cout.tie(0);
//    int t;
//    cin >> t;
//    while (t--)solve();
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//int arr[200];
//int main()
//{
//    int t;
//    cin >> t;
//    while (t--)
//    {
//        int n;
//        cin >> n;
//        if (n % 2 == 0)
//            cout << -1 << endl;
//        else {
//            cout << n << ' ';
//            for (int i = 1; i < n; i++)cout << i << ' ';
//            cout << endl;
//        }
//    }
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//const int N = 2e5 + 10;
//LL arr[N];
//LL brr[N];
//map<LL, LL>mp1;
//vector<LL>v1;
//vector<LL>v2;
//int main()
//{
//    LL t;
//    cin >> t;
//    while (t--)
//    {
//        int n;
//        cin >> n;
//        int flag = 0;
//        for (int i = 1; i <= n; i++) {
//            cin >> arr[i]; mp1[arr[i]] = i; 
//        }
//        for (int i = 1; i <= n; i++) {
//            cin >> brr[i];
//            if (brr[i] == arr[i])flag++;
//        }
//        if (n % 2 == 0 && flag)
//            cout << -1 << endl;
//        else if (n % 2 && flag != 1)cout << -1 << endl;
//        else
//        {
//            for (int i = 1; i <= n; i++)
//            {
//                if (brr[i] != arr[n + 1 - i])
//                {
//                    int pos_a = mp1[brr[i]];
//                    if (pos_a == i)
//                    {
//                        int mid = (1 + n) / 2;
//                        mp1[arr[i]] = mid;
//                        mp1[arr[mid]] = i;
//                        swap(arr[i], arr[mid]);
//                        swap(brr[i], brr[mid]);
//                        v1.push_back(i);
//                        v2.push_back(mid);
//                    }
//                    else {
//                        mp1[arr[pos_a]] = n - i + 1;
//                        mp1[arr[n - i + 1]] = pos_a;
//                        swap(arr[pos_a], arr[n - i + 1]);
//                        swap(brr[pos_a], brr[n - i + 1]);
//                        v1.push_back(pos_a);
//                        v2.push_back(n - i + 1);
//                    }
//                }
//            }
//            flag = 0;
//            for (int i = 1; i <= n; i++)
//                if (arr[i] != brr[n + 1 - i])flag = 1;
//            if (flag)
//                cout << -1 << endl;
//            else {
//                cout << v1.size() << endl;
//                for (int i = 0; i < v1.size(); i++)
//                    cout << v1[i] << ' ' << v2[i] << endl;
//            }
//            v1.clear();
//            v2.clear();
//        }
//
//    }
//    return 0;
//}
//#include <cstring>
//#include <iostream>
//#include <algorithm>
//#include <cmath>
//
//#define x first
//#define y second
//
//using namespace std;
//
//typedef pair<double, double> PDD;
//
//const int N = 18, M = 1 << 18;
//const double eps = 1e-8;
//
//int n, m;
//PDD q[N];
//int path[N][N];
//int f[M];
//
//int cmp(double x, double y)
//{
//    if (fabs(x - y) < eps) return 0;
//    if (x < y) return -1;
//    return 1;
//}
//
//int main()
//{
//    int T;
//    cin >> T;
//    while (T--)
//    {
//        cin >> n >> m;
//        for (int i = 0; i < n; i++) cin >> q[i].x >> q[i].y;
//
//        memset(path, 0, sizeof path);
//        for (int i = 0; i < n; i++)
//        {
//            path[i][i] = 1 << i;
//            for (int j = 0; j < n; j++)
//            {
//                double x1 = q[i].x, y1 = q[i].y;
//                double x2 = q[j].x, y2 = q[j].y;
//                if (!cmp(x1, x2)) continue;
//                double a = (y1 / x1 - y2 / x2) / (x1 - x2);
//                double b = y1 / x1 - a * x1;
//
//                if (cmp(a, 0) >= 0) continue;
//                int state = 0;
//                for (int k = 0; k < n; k++)
//                {
//                    double x = q[k].x, y = q[k].y;
//                    if (!cmp(a * x * x + b * x, y)) state += 1 << k;
//                }
//                path[i][j] = state;
//            }
//        }
//
//        memset(f, 0x3f, sizeof f);
//        f[0] = 0;
//        for (int i = 0; i + 1 < 1 << n; i++)
//        {
//            int x = 0;
//            for (int j = 0; j < n; j++)
//                if (!(i >> j & 1))
//                {
//                    x = j;
//                    break;
//                }
//
//            for (int j = 0; j < n; j++)
//                f[i | path[x][j]] = min(f[i | path[x][j]], f[i] + 1);
//        }
//
//        cout << f[(1 << n) - 1] << endl;
//    }
//
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//class Solution {
//public:
//    int dp[1010];
//    vector<int> largestDivisibleSubset(vector<int>& nums) {
//        sort(nums.begin(), nums.end());
//        
//        int n = nums.size();
//        int Max = 0;
//        for (int i = 1; i <= n;i++)dp[i] = 1;
//        for (int i = 1; i <= n; i++) {
//            for (int j = 1; j < i; j++) {
//                if (nums[i - 1] % nums[j - 1] == 0)
//                    dp[i] = max(dp[i], dp[j] + 1);
//            }
//            Max = max(Max, dp[i]);
//        }
//        int pos = 0;
//        vector<int>ans;
//        for (int i = 1; i <= n; i++)if (dp[i] == Max)pos = i;
//        ans.push_back(nums[pos-1]);
//        int j = pos - 1;
//        while (Max>1)
//        {
//            if (nums[pos - 1] % nums[j-1] == 0 && dp[pos] == dp[j] + 1)
//            {
//                Max--;
//                pos = j;
//                ans.push_back(nums[pos-1]);
//            }
//            j--;
//       }
//        reverse(ans.begin(), ans.end());
//        return ans;
//    }
//};
//int main()
//{
//    vector<int>v{ 5,9,18,54,108,540,90,180,360,720 };
//    vector<int>ans=Solution().largestDivisibleSubset(v);
//    for (auto i : ans)cout << i << ' ';
//}
//#include <iostream>
//#include <cstdio>
//#include <cstring>
//#include <algorithm>
//#include <vector>
//
//using namespace std;
//
//const int N = 12, M = 102;
//
//int f[N][10][M];  //f[i][j][k] ��ʾһ����iλ�������λ������j��������λ���ֺ�ģpλk�����ָ���
//int p;
//
//int mod(int u, int v) {
//    return (u % v + v) % v;  //c++��%��õ���������Ҫ��һ��ƫ��
//}
//
//void init() {
//    memset(f, 0, sizeof f);   //����������ݣ�f����Ҫ���
//    for (int i = 0; i <= 9; i++) f[1][i][i % p]++;
//
//    for (int i = 2; i < N; i++)
//        for (int j = 0; j <= 9; j++)
//            for (int k = 0; k < p; k++)
//                for (int x = 0; x <= 9; x++)
//                    f[i][j][k] += f[i - 1][x][mod(k - j, p)];
//}
//
//int dp(int n) {
//    if (!n) return 1;
//    int res = 0, last = 0;
//
//    vector<int> a;
//    while (n) a.push_back(n % 10), n /= 10;
//
//    int len = a.size() - 1;
//    for (int i = len; i >= 0; --i) {
//        int x = a[i];
//        for (int j = 0; j < x; j++)  //��iλ��0~x-1
//            res += f[i + 1][j][mod(-last, p)]; //0~iλ������һ����i+1λ
//
//        last += x;
//        if (!i && last % p == 0) res++;
//    }
//    return res;
//}
//int main()
//{
//
//    int l, r;
//    while (cin >> l >> r >> p) {
//        init();
//        cout << dp(r) - dp(l - 1) << endl;
//    }
//
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//char arr[30];
//char brr[6][6];
//const int N = 5;
//bool check() {
//	//�Ƿ����
//	for (int i = 0; i < N*N; i++)brr[i / N][i % N] = arr[i];
//	for (int i = 0; i < N; i++)
//		if (brr[i][0] == brr[i][1] && brr[i][0] == brr[i][2] && brr[i][0] == brr[i][3] && brr[i][0] == brr[i][4])
//			return 0;
//	for (int i = 0; i < 5; i++)
//		if (brr[0][i] == brr[1][i] && brr[0][i] == brr[2][i] && brr[0][i] == brr[3][i] && brr[0][i] == brr[4][i])
//			return 0;
//	if (brr[0][0] == brr[1][1] && brr[1][1] == brr[2][2] && brr[3][3]==brr[2][2] && brr[4][4] == brr[3][3])return 0;
//	if (brr[4][0] == brr[3][1] && brr[3][1] == brr[2][2] && brr[2][2] == brr[1][3] && brr[1][3] == brr[0][4])return 0;
//	return 1;
//}
//long long cnt = 0;
//void dfs(int num,int bai,int hei) {
//	if (num == 25) { if (bai==13&&hei==12&&check())cnt++; return; }
//	arr[num] = '0';
//	dfs(num + 1,bai+1,hei);
//	arr[num] = '1';
//	dfs(num + 1,bai,hei+1);
//}
//int main()
//{
//	dfs(0,0,0);
//	cout << cnt;
//}
//#include <bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//const int N = 1e5 + 10;
//struct date {
//    LL a, b;
//    bool operator<(const date d)const
//    {
//        return b > d.b;
//    }
//} arr[N];
//priority_queue<date>pq;
//int main()
//{
//    int n, s;
//    LL sum = 0;
//    LL ans = 0;
//    cin >> n >> s;
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> arr[i].a >> arr[i].b; sum += arr[i].a;
//        pq.push(arr[i]);
//    }
//    LL cnt = 0;//ѵ���˶��ٴ�
//    while (pq.size() && sum >= s)
//    {
//        auto it = pq.top();
//        pq.pop();
//        if (it.b <= cnt) {
//            sum -= it.a;
//            continue;
//        }
//        cnt = it.b;
//        sum -= it.a;
//        ans = it.b * s;
//    }
//    while (pq.size())
//    {
//        auto it = pq.top();
//        pq.pop();
//        ans += it.a * (it.b - cnt);
//    }
//    cout << ans;
//    return 0;
//}
//#include <iostream>
//using namespace std;
//typedef long long LL;
//const int N = 4e5 + 10;
//int idx1 = 0;
//int idx2 = 0;
//int e[N], ne[N], h[N];
//int E[N], NE[N], H[N];
//LL w[N], W[N];
//void add(int a, int b) {
//	e[idx1] = b, ne[idx1] = h[a], h[a] = idx1;
//}
//void ADD(int a, int b) {
//	E[idx2] = b, NE[idx2] = H[a], H[a] = idx2++;
//}
//int f(int root1, int root2,int fa1,int fa2) {
//	if (w[root1] != w[root2])return 0;
//	int Max = 0;
//	for (int i = h[root1]; i != -1; i = ne[i]) {
//		if (e[i] == fa1)continue;
//		for (int j = H[root2]; ~j; j = NE[j]) {
//			if (e[j] == fa2)continue;
//			Max = max(Max, f(e[i], E[j], root1, root2));
//		}
//	}
//	return Max + 1;
//}
//int main()
//{
//	int n, m;
//	cin >> n >> m;
//	memset(h, -1, sizeof h);
//	memset(H, -1, sizeof H);
//	for (int i = 1; i <= n; i++)cin >> w[i];
//	for (int i = 1; i <= m; i++)cin >> W[i];
//	for (int i = 1; i < n; i++) {
//		int a, b;
//		cin >> a >> b;
//		add(a, b);
//		add(b, a);
//	}
//	for (int i = 1; i < m; i++) {
//		int a, b;
//		cin >> a >> b;
//		ADD(a, b);
//		ADD(b, a);
//	}
//	cout << f(1, 1, -1, -1);;
//	return 0;
//}
//#include <iostream>
//#include<algorithm>
//using namespace std;
//typedef long long LL;
//const int N = 2e5 + 10;
//LL arr[N];
//int n, k;
//double t;
//LL brr[N];
//LL sum[N];
//bool check(int len)
//{
//	memcpy(brr, arr, sizeof brr);
//	sort(brr + 1, brr + 1 + len);
//	for (int i = 1; i <= len; i++)sum[i] = sum[i - 1] + brr[i] * brr[i];
//	LL sum_ = 0;
//
//	for (int i = 1,j=1; j <= len; j++)
//	{
//		sum_ += brr[j];
//		if (j - i >= k)sum_ -= brr[i++];
//		if (j >= k)
//			if ((sum[j] - sum[j - k]) - k + (sum_ * sum_) < t * k)
//			return true;
//	}
//	return false;
//}
//int main()
//{
//	// ���ڴ��������Ĵ���
//	cin >> n >> k >> t;
//	for (int i = 1; i <= n; i++)cin >> arr[i];
//	int l = 1, r = n;
//	while (l < r)
//	{
//		int mid = l + r >> 1;
//		if (check(mid))r = mid;
//		else
//			l = mid + 1;
//	}
//	if (check(r))
//		cout << r;
//	else
//		cout << -1;
//	return 0;
//}
//#include<bits/stdc++.h>
//
//using namespace std;
//typedef long long LL;
//const int N = 2e5 + 10;
//LL arr[N];
//int cnt[N];
//int main()
//{
//	int n;
//	cin >> n;
//	LL a = 0, b = 0;
//	LL Max = 0;
//	for (int i = 1; i <= n; i++) {
//		cin >> arr[i]; cnt[arr[i]]++; Max = max(Max, arr[i]);
//}
//	sort(arr + 1, arr + 1 + n);
//	LL ans = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		for (LL j = arr[i]; j <= Max; j += arr[i])
//		{
//			if (j % arr[i] == 0&&cnt[j])
//			{
//				if (j == arr[i]) { a += cnt[j] - 1;ans+=() }
//				else
//					b += cnt[j];
//			}
//		}
//	}
//	LL ans = b * (b - 1);
//	ans+=
//}
//#include<bits/stdc++.h>
//using namespace std;
//const int N = 2e5 + 10;
//int e[N], ne[N], h[N];
//int idx;
//int w[N];
//int s, d;
//int dis[N];
//void add(int a, int b)
//{
//	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
//}
//int lowbit(int x)
//{
//	return x & -x;
//}
//int cnt(int num)
//{
//	int ans = 0;
//	while (num)
//	{
//		ans++;
//		num -= lowbit(num);
//	}
//	return ans;
//}
//unordered_map<int, int>mp;
//bool is[N];
//int bfs()
//{
//	queue<int>q;
//	q.push(s);
//	dis[s] = 0;
//	int juli = -1;
//	int ans = 0;
//	is[s] = 0;
//	mp[s] = 1 << w[s];
//	while (q.size())
//	{
//		auto it = q.front();
//		q.pop();
//		if (is[it])continue;
//		is[it] = 1;
//		if (it == d)
//		{
//			if (juli == -1)
//			{
//				juli = dis[it];
//				ans = cnt(mp[d]);
//			}
//			else {
//				if (juli < dis[it])return ans;
//				ans = max(ans, cnt(mp[d]));
//			}
//		}
//		for (int i = h[it]; ~i; i = ne[i])
//		{
//			int j = e[i];
//			if (dis[j] > dis[it] + 1)
//			{
//				dis[j] = dis[it] + 1;
//				mp[j] = mp[it] | (1 << w[j]);
//				q.push(j);
//			}
//			else if (dis[j] == dis[it] + 1)
//			{
//				if (cnt(mp[j]) < cnt(mp[it] | (1 << w[j])))
//				{
//					mp[j] = mp[it] | (1 << w[j]);
//					q.push(j);
//				}
//			}
//		}
//	}
//	return ans;
//}
//int main()
//{
//	memset(h,-1, sizeof h);
//	int n, q;
//	cin >> n >> q;
//	for (int i = 1; i <= n; i++)cin >> w[i];
//	for (int i = 0; i < n - 1; i++)
//	{
//		int a, b;
//		cin >> a >> b;
//		add(a, b);
//		add(b, a);
//	}
//	while (q--)
//	{
//		mp.clear();
//		memset(is, 0, sizeof is);
//		memset(dis, 0x3f, sizeof dis);
//		cin >> s >> d;
//		cout<<bfs()<<endl;
//	}
//	return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//const int N = 2e5 + 10;
//struct date {
//	int a, b;
//	bool operator<(const date d)const
//	{
//		return a > d.a;
//	}
//}arr[N];
//int main()
//{
//	int n, k;
//	cin >> n >> k;
//	for (int i = 1; i <= n; i++)cin >> arr[i].a, arr[i].b = i;
//	sort(arr + 1, arr + 1 + n);
//	for (int i = 1; i <= n; i++)
//	{
//		if (arr[i].b < i)cout << -1 << ' ';
//		else	if (k > arr[i].b-i)cout << arr[i].a << ' ',k-=(arr[i].b-i);
//		else
//			cout << -1 << ' ';
//	}
//}
//#include<bits/stdc++.h>
//using  namespace std;
//typedef long long LL;
//LL arr[200000];
//bool is[200000];
//int main()
//{
//	int n;
//	cin >> n;
//	LL ans = 0;
//	for (int i = 1; i <= n; i++)cin >> arr[i];
//	for(int i=1;i<=n;i++)
//		for (int j = 1; j <= n; j++)
//		{
//			if (i == j)continue;
//			if (arr[j] % arr[i])continue;
//			is[i] = true;
//			is[j] = true;
//			for (int x = 1; x <= n; x++)
//			{
//				if (is[x])continue;
//				for (int y = 1; y <= n; y++)
//				{
//					if (y == x)continue;
//					if (is[y])continue;
//					if (arr[y] % arr[x] == 0)ans++;
//				}
//			}
//			is[i] = false;
//			is[j] = false;
//		}
//	cout << ans;
//}
//#include<bits/stdc++.h>
//using namespace std;
//const int N = 2e5 + 10;
//int idx;
//int e[N], ne[N], h[N];
//int dis[N];
//int w[N];
//int cnt[N][25];
//void add(int a, int b)
//{
//    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
//}
//bool is[N];
//queue<int>q;
//int fa[N][25];
//void bfs(int root)
//{
//    q.push(1);
//    is[1] = true;
//    dis[0] = 0;
//    dis[1] = 1;
//    while (q.size())
//    {
//        auto it = q.front();
//        q.pop();
//        for (int i = h[it]; ~i; i = ne[i])
//        {
//            int j = e[i];
//            if (dis[j] > dis[it] + 1)
//            {
//                q.push(j);
//                is[j] = true;
//                dis[j] = dis[it] + 1;
//                fa[j][0] = it;
//                for (int k = 1; k <= 20; k++)fa[j][k] = fa[fa[j][k - 1]][k - 1];
//            }
//        }
//    }
//}
//void dfs(int root, int fa)//��ǰ׺
//{
//    cnt[root][w[root]]++;
//    for (int i = h[root]; ~i; i = ne[i])
//    {
//        int j = e[i];
//        if (j == fa)continue;
//        for (int k = 0; k < 25; k++)
//            cnt[j][k] = max(cnt[j][k], cnt[root][k]);
//        dfs(j, root);
//    }
//}
//int lca(int a, int b)
//{
//    if (dis[a] < dis[b])swap(a, b);
//    for (int k = 20; k >= 0; k--)
//    {
//        if (dis[fa[a][k]] >= dis[b])
//            a = fa[a][k];
//    }
//    if (a == b)return a;
//    for (int k = 20; k >= 0; k--)
//    {
//        if (fa[a][k] != fa[b][k])
//            a = fa[a][k], b = fa[b][k];
//    }
//    return fa[a][0];
//}
//int main()
//{
//    int n, q;
//    cin >> n >> q;
//    memset(h, -1, sizeof h);
//    memset(dis, 0x3f, sizeof dis);
//    for (int i = 1; i <= n; i++)cin >> w[i];
//    for (int i = 0; i < n - 1; i++) {
//        int a, b;
//        cin >> a >> b;
//        add(a, b);
//        add(b, a);
//    }
//    bfs(1);
//    dfs(1, -1);
//    while (q--)
//    {
//        int a, b;
//        cin >> a >> b;
//        int p = lca(a, b);
//        int num = 0;
//        for (int i = 0; i <= 20; i++)
//        {
//            int ans = cnt[a][i] + cnt[b][i] - cnt[p][i] * 2;
//            if (w[p] == i)ans += 1;
//            if (ans > 0)num++;
//        }
//        cout << num << endl;
//    }
//}
//#include<bits/stdc++.h>
//using namespace std;
//int n;
//typedef long long LL;
//const int N = 2e5 + 10;
//LL arr[N];
//LL cnt[N];
//LL yinzi[N];//i�м�������
//LL beishu[N];//�м�������
//int main()
//{
//    cin >> n;
//    LL Max = 0;
//    LL m = 0;
//    for (int i = 1; i <= n; i++)
//        cin >> arr[i], Max = max(Max, arr[i]), cnt[arr[i]]++;
//    for (int i = 1; i <= Max; i++)//ö�������е���
//    {
//        if (!cnt[i])continue;//���������������
//        for (int j = i; j <= Max; j += i)
//        {
//            if (cnt[j] == 0)continue;
//            if (j % i == 0)
//            {
//                beishu[i] += cnt[j];
//                yinzi[j] += cnt[i];
//                if (i == j)
//                    beishu[i]--,yinzi[j]--;
//            }
//        }
//        m += beishu[i] * cnt[i];
//    }
//    LL ans = m * m;
//    for (int i = 1; i <= Max; i++)
//        if (cnt[i])
//        {
//            ans -= beishu[i] * (beishu[i]) * cnt[i];//A
//            ans -= beishu[i] * yinzi[i] * cnt[i] * 2;//B+C
//            ans -= yinzi[i] * yinzi[i] * cnt[i];//D
//            ans += beishu[i] * cnt[i];//AD
//            ans += cnt[i] * (cnt[i] - 1);//BD
//        }
//    cout << ans;
//    return 0;
//}
//#include<iostream>
//#include<vector>
//#include<algorithm>
//#include<cstring>
//
//using namespace std;
//
//using ll = long long;
//const int N = 1e5 + 10;
//
//ll n, m, cnt[N], ftr[N], mul[N], dmax, ans;
//
//int main() {
//
//
//    cin >> n;
//
//    for (int i = 0; i < n; i++) {
//        int a;
//        cin >> a;
//        cnt[a]++;
//        dmax = max(dmax, (ll)a);
//    }
//
//    for (int i = 1; i <= dmax; i++) {
//        for (int j = i; j <= dmax; j += i) {
//            if (cnt[j]) ftr[j] += cnt[i];
//            if (cnt[i]) mul[i] += cnt[j];
//            if (i == j && cnt[i]) ftr[j]--, mul[j]--;
//        }
//        m += cnt[i] * mul[i];
//    }
//
//    ans = m * m;
//
//    for (int i = 1; i <= dmax; i++) {
//        ans -= mul[i] * mul[i] * cnt[i];//A
//        ans -= ftr[i] * ftr[i] * cnt[i];//B
//        if (ftr[i] && mul[i]) ans -= (cnt[i] * ftr[i] * mul[i]) * 2;//C��D
//        ans += cnt[i] * (cnt[i] - 1);//C��D
//    }
//
//    ans += m;//A��B
//
//
//    cout << ans;
//
//    return 0;
//}

//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//const LL N = 1e8;
//int main()
//{
//	LL ans = 0;
//	for (LL i = 1; i <= N; i++)
//	{
//		string s = to_string(i);
//		if (s.size() % 2)continue;
//		LL a = 0, b = 0;
//		for (int i = 0; i < s.size(); i++)
//		{
//			if (i < s.size() / 2)
//			{
//				a += (s[i] - '0');
//			}
//			else
//			{
//				b += s[i] - '0';
//			}
//		}
//		if (a == b)ans++;
//	}
//	cout << ans;
//}
//#include<iostream>
//using namespace std;
//int n;
//int ans;
//int N;
//void dfs(int n, int sum)
//{
//	if (sum == 100)return;
//	if (n == N )
//	{
//		if(sum==70)
//		ans++;
//		return;
//	}
//	dfs(n + 1, sum + 10);
//	dfs(n + 1, 0);
//	if (sum == 70)ans++;
//}
//int main()
//{
//	N = 30;
//	dfs(0, 0);
//	cout << ans;
//}
//#include<bits/stdc++.h>
//using namespace std;
//int ii = 0;
//bool com(vector<int>& v1, vector<int>& v2)
//{
//    if (v1.size() != v2.size())return v1.size() > v2.size();
//    for (int i = v1.size() - 1; i >= 0; i--)
//    {
//        if (v1[i] != v2[i])return v1[i] > v2[i];
//    }
//    return 1;
//}
//
//vector<int>add(vector<int>v1, vector<int>v2)
//{
//    if (com(v1, v2) == 0)swap(v1, v2);
//    vector<int>v;
//    int flag = 0;
//    for (int i = 0; i < v1.size(); i++)
//    {
//        int x = v1[i] + flag;
//        if (i < v2.size())x += v2[i];
//        v.push_back(x % 10);
//        flag = (x / 10);
//    }
//    v.push_back(flag);
//    while (v.size() > 1 && v[v.size() - 1] == 0)v.pop_back();
//    return v;
//}
//vector<int> cheng(vector<int>& v1, vector<int>& v2)
//{
//    vector<int>ans;
//    int flag = 0;
//    for (int i = 0; i < v1.size(); i++) {
//        vector<int>v;
//        for (int k = 0; k < i; k++)v.push_back(0);
//        for (int j = 0; j < v2.size(); j++)
//        {
//           
//            int x = v1[i] * v2[j] + flag;
//            v.push_back(x % 10);
//            flag = x / 10;
//        }
//        while (flag)
//        {
//            v.push_back(flag % 10);
//            flag /= 10;
//        }
//        while (v.size() > 1 && v[v.size() - 1] == 0)v.pop_back();
//       ans= add(ans, v);
//    }
//    return ans;
//}
//vector<int>jian(vector<int>v1, vector<int>v2)
//{
//    if (com(v1, v2) == 0)swap(v1, v2), ii = 1;
//    int flag = 0;
//    vector<int>v;
//    for (int i = 0; i < v1.size(); i++)
//    {
//        int t = v1[i];
//        t -= flag;
//        if (i < v2.size())
//            t -= v2[i];
//        v.push_back((t + 10) % 10);
//        flag = t < 0;
//    }
//    while (v.size() > 1 && v[v.size() - 1] == 0)v.pop_back();
//    return v;
//}
//int main()
//{
//    string s1, s2;
//    cin >> s1 >> s2;
//    vector<int>v1, v2;
//    
//    for (int i = s1.size()-1; i >= 0; i--)
//    {
//        if (s1[i] == '-')continue;
//        v1.push_back(s1[i] - '0');
//    }
//    for (int i = s2.size()-1; i >= 0; i--)
//    {
//        if (s2[i] == '-')continue;
//        v2.push_back(s2[i] - '0');
//    }
//    v1 = cheng(v1, v1);
//    v2 = cheng(v2, v2);
//    v1 = jian(v1, v2);
//    if (ii)cout << "-";
//    for (int i = v1.size() - 1; i >= 0; i--)cout << v1[i];
//}
//#include <iostream>
//using namespace std;
//const int N = 2e8 + 10;
//bool arr[N];
//int main()
//{
//    int n;
//    cin >> n;
//    if (n == 1) { cout << 1; return 0; }
//    int sum = 1;
//    for (int i = 2; i <= n; i++)
//    {
//        if (arr[i]);
//        else {
//            sum++;
//            for (int j = 2 * i; j <= n; j += i)arr[j] ^= 1;
//        }
//    }
//    cout << sum;
//    return 0;
//}
//#include <iostream>
//using namespace std;
//int arr[2000][2000];
//int n;
//int idx;
//int e[4000], ne[4000], h[2010];
//int w[2010];
//void add(int a, int b)
//{
//    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
//}
//void dfs(int root)
//{
//    for (int i = h[root]; ~i ; i = ne[i])
//    {
//        int j = e[i];
//        dfs(j);
//        for (int k = 1; k < 2000; k++)arr[root][k] += arr[j][k];
//    }
//    arr[root][w[root]]++;
//}
//int main()
//{
//    // ���ڴ��������Ĵ���
//    cin >> n;
//    memset(h, -1, sizeof h);
//    int root = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        int a, b;
//        cin >> a >> b;
//        if (b == 0)root = i, w[i] = a;
//        else {
//            w[i] = a;
//            add(b, i);
//        }
//    }
//    dfs(root);
//    int sum = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        int flag = 1;
//        int j = 1;
//        while (arr[i][j] == 0)j++;
//        int x = arr[i][j];
//        for (j; j < 2000; j++) {
//            if (arr[i][j] && arr[i][j] != x) { flag = 0; break; }
//        }
//        sum += flag;
//    }
//    cout << sum;
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//LL n, m;
//LL ans = 50;
//LL w[50];
//int flag = 0;
//void dfs(LL pos, LL sum, LL dao)
//{
//    cout << pos << ' ' << sum << ' ' << dao << endl;
//    if (dao >= ans)return;
//    if (sum > m)return;
//    if (pos == n)
//    {
//        if (sum == m)flag = 1, ans = dao;
//        return;
//    }
//    dfs(pos + 1, sum, dao);
//    dfs(pos + 1, sum + w[pos], dao);
//    dfs(pos + 1, sum + w[pos] / 2, dao + 1);
//}
//int main()
//{
//    // ���ڴ��������Ĵ���
//    cin >> n >> m;
//    m *= 2;
//    dfs(0, 0, 0);
//    for (int i = 0; i < n; i++)cin >> w[i], w[i] *= 2;
//    sort(w, w + n, greater<LL>());
//    if (ans == 0 && flag == 0)cout << -1;
//    else cout << ans;
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//LL n, m;
//LL ans = 50;
//LL w[50];
//int flag = 0;
//LL A[50];
//unordered_map<LL, pair<bool,int>>mp;
//void dfs(LL pos, LL sum, LL dao)
//{
//    //  cout<<pos<<' '<<sum<<' '<<dao<<endl;
//    if (sum > m)return;
//    if (sum + A[n/2] - A[pos] < sum)return;
//    if (pos == n/2)
//    {
//        if (mp.count(sum) == 0)mp[sum] = { true,dao };
//        else if (mp[sum].second > dao)mp[sum] = { true,dao };
//        return;
//    }
//    dfs(pos + 1, sum, dao);
//    dfs(pos + 1, sum + w[pos], dao);
//    dfs(pos + 1, sum + w[pos] / 2, dao + 1);
//}
//void dfs_(int pos, LL sum, LL dao)
//{
//    if (sum > m)return;
//    if (dao >= ans)return;
//    if (pos == n)
//    {
//        if (mp.count(m - sum))ans = dao+mp[m-sum].second; return;
//    }
//    dfs_(pos + 1, sum, dao);
//    dfs_(pos + 1, sum + w[pos], dao);
//    dfs_(pos + 1, sum + w[pos] / 2, dao + 1);
//}
//int main()
//{
//    // ���ڴ��������Ĵ���
//    cin >> n >> m;
//    m *= 2;
//
//    for (int i = 0; i < n; i++)cin >> w[i], w[i] *= 2;
//    sort(w, w + n, greater<LL>());
//    for (int i = 0; i < n; i++)A[i + 1] = A[i] + w[i];
//    dfs(0, 0, 0);
//    dfs_(n / 2, 0, 0);
//    if (ans == 50 && flag == 0)cout << -1;
//    else cout << ans;
//    return 0;
//}
//#include <iostream>
//using namespace std;
//const int N = 1e5 + 10;
//int e[N * 2], ne[N * 2], h[N];
//inr idx;
//int w[N * 2];
//void add(int a, int b)
//{
//	e[idx] = b, ne[idx] = h[a], h[a] = idx; w[idx] = c; idx++;
//}
//int n, m, q;
//int main()
//{
//	memset(h, -1, sizeof h);
//	// ���ڴ��������Ĵ���
//	cin >> n >> m >> q;
//	for (int i = 0; i < m; i++)
//	{
//		LL a, b, c;
//		cin >> a >> b >> c;
//		add(a, b, c);
//		add(b, a, c);
//	}
//	while (q--)
//	{
//		int a, b;
//		cin >> a >> b;
//		memset(dis, 0x3f)
//			di(a, b);
//
//	}
//#include<bits/stdc++.h>
//using namespace std;
//int n, m;
//char brr[20][20];
//char arr[20][20];
//int ans;
//int flag = 0;
//int cnt(int x, int y)
//{
//    int num = 0;
//    for (int i = x - 1; i <= x + 1; i++)
//        for (int j = y - 1; j <= y + 1; j++)
//        {
//            if (i && j && i <= n && j <= m && brr[i][j] == '1')num++;
//        }
//    return num;
//}
//bool is()
//{
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//        {
//            if (arr[i][j] == '_')continue;
//            int num = cnt(i, j);
//            if (num + '0' == arr[i][j]);
//            else return 0;
//        }
//    return 1;
//}
//void dfs(int i)
//{
//    if (flag)return;
//    if (i == n * m) {
//        if (is())
//        {
//            for (int i = 1; i <= n; i++) {
//                for (int j = 1; j <= m; j++)cout << brr[i][j];
//                cout << endl;
//            }
//            flag = 1;
//        }
//        return;
//    }
//    brr[i / m+1][i % m+1] = '0';
//    dfs(i + 1);
//    brr[i / m+1][i % m+1] = '1';
//    dfs(i + 1);
//}
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)cin >> arr[i][j];
//    dfs(0);
//}
//#include <bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//map<long long, LL>mp;
//map<LL, LL>mp1;
//const LL MOD = 1e9 + 7;
//const LL N = 1e5 + 10;
//LL arr[N];
//int main()
//{
//    int n, D;
//    cin >> n >> D;
//    for (int i = 1; i <= n; i++)
//        cin >> arr[i];
//    for (int i = 1; i <= n; i++)
//    {
//        mp1[arr[i]]++;
//        if (i - D > 1)mp1[arr[i-D-1]]--;
//        mp[arr[i]] += mp1[arr[i]];
//
//    }
//    LL ans = 1;
//    for (auto i : mp)
//        ans = ans * (i.second + 1) % MOD;
//    ans--;
//    cout << ans;
//    return 0;
//}
//#include <bits/stdc++.h>
//using namespace std;
//const int N = 200010;
//unordered_map<int, int>sum[N], cnt[N];
//int col[N];
//vector<int>e[N];
//int ans = 0;
//int n;
//
//void dfs(int u)
//{
//    cnt[u][col[u]]++;
//    sum[u][1]++;
//    for (auto k : e[u]) {
//        dfs(k);
//        if (cnt[k].size() > cnt[u].size()) {
//            swap(cnt[k], cnt[u]);
//            swap(sum[k], sum[u]);
//        }
//        for (auto c : cnt[k]) {
//            int co = c.first, cn = c.second;
//                if (cnt[u].count(co) && !--sum[u][cnt[u][co]]) {
//                    sum[u].erase(cnt[u][co]);
//                }
//            cnt[u][co] += cn;
//            sum[u][cnt[u][co]]++;
//        }
//    }
//    if (sum[u].size() == 1) {
//        ans++;
//    }
//}
//
//int main()
//{
//    cin >> n;
//    for (int i = 1; i <= n; i++) {
//        int a;
//        cin >> col[i] >> a;
//        e[a].push_back(i);
//    }
//    dfs(1);
//    cout << ans;
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//int n, m;
//char brr[20][20];
//char arr[20][20];
//int ans;
//int flag = 0;
//
//int cnt(int x, int y)
//{
//    int num = 0;
//    for (int i = x - 1; i <= x + 1; i++)
//        for (int j = y - 1; j <= y + 1; j++)
//        {
//            if (i && j && i <= n && j <= m && brr[i][j] == '1')num++;
//        }
//    return num;
//}
//bool isxy(int x, int y)
//{
//    if (arr[x][y] == '_')return 1;
//    int num = cnt(x, y);
//    return num + '0' == arr[x][y];
//}
//bool is()
//{
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//        {
//            if (arr[i][j] == '_')continue;
//            int num = cnt(i, j);
//            if (num + '0' == arr[i][j]);
//            else return 0;
//        }
//    return 1;
//}
//void dfs(int i)
//{
//    if (flag)return;
//    int x = i / m + 1;
//    int y = i % m + 1;
//   
//    if (i == n * m) {
//        if (is())
//        {
//            for (int i = 1; i <= n; i++) {
//                for (int j = 1; j <= m; j++)cout << brr[i][j];
//                cout << endl;
//            }
//            flag = 1;
//        }
//        return;
//    }
//    brr[i / m + 1][i % m + 1] = '0';
//    if (x > 1 && y > 1 && isxy(x - 1, y - 1) == 1)
//        dfs(i + 1);
//    else if (x == 1 || y == 1)
//        dfs(i + 1);
//    brr[i / m + 1][i % m + 1] = '1';
//    if (x > 1 && y > 1 && isxy(x - 1, y - 1) == 1)
//        dfs(i + 1);
//    else if (x == 1 || y == 1)
//        dfs(i + 1);
//}
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)cin >> arr[i][j];
//    dfs(0);
//}
//#include <iostream>
//using namespace std;
//typedef long long LL;
//int main()
//{
//    // ���ڴ��������Ĵ���
//    LL x1, y1, x2, y2, x3, y3 ,x4, y4;
//    cin >> x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;
//    LL sum = 0;
//    sum += (x2 - x1) * (y2 - y1);
//    sum += (x4 - x3) * (y4 - y3);
//    if (x1 <= x3 && x3 <= x2)
//    {
//        LL x = min(x2, x4) - x3;
//        LL y = 0;
//        if (y2<=y4&&y2>=y3)
//            y = y2 - max(y3, y1);
//        else if (y2>=y4&&y4>=y1)
//        {
//            y = y4 - max(y3, y1);
//        }
//        sum -= x * y;
//    }
//    else if (x1>=x3&&x1<=x4)
//    {
//        LL x = min(x2, x4) - x1;
//        LL y = 0;
//        if (y2 <= y4 && y2 >= y3)
//            y = y2 - max(y3, y1);
//        else if (y2 >= y4 && y4 >= y1)
//        {
//            y = y4 - max(y3, y1);
//        }
//        sum -= x * y;
//    }
//
//    cout << sum;
//    return 0;
//}
//#include <iostream>
//using namespace std;
//typedef long long LL;
//int arr[100000000];
//bool is[100000000];
//int cnt = 0;
//void init()
//{
//    for (int i = 2; i < 100000000; i++)
//    {
//        if (is[i] == 0)arr[++cnt] = i;
//        for (int j = 1; arr[j] * i <= 100000000; j++)
//        {
//            is[arr[j] * i] = true;
//            if (i % arr[j] == 0)break;
//        }
//    }
//}
//int main()
//{
//    // ���ڴ��������Ĵ���
//    int t;
//    cin >> t;
//    init();
//    while (t--)
//    {
//        LL x;
//        cin >> x;
//        int num = 0;
//        int flag = 0;
//        for (int i = 1; i <= cnt && (LL)arr[i] * arr[i] <= x; i++)
//        {
//            if (x % arr[i] == 0)
//            {
//                int sum = 0;
//                while (x % arr[i] == 0) {
//                    x /= arr[i];
//                    sum++;
//                }
//                if (sum % 2) {
//                    cout << "no" << endl;
//                    flag = 1;
//                    break;
//                }
//                num++;
//            }
//        }
//        if (flag == 0)
//        {
//            if (x != 1)
//                cout << "no" << endl;
//            else
//                cout << "yes" << endl;
//        }
//
//    }
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef pair<double, double> PDD;
//set<PDD>s;
//int main()
//{
//	for(int i=0;i<21;i++)
//		for(int j=0;j<20;j++)
//			for(int k=i+1;k<21;k++)
//				for (int l = 0; l < 20; l++)
//				{
//                    if (l == j)continue;
//                    double x = (double)(k - i) / (l - j);
//					double y =(double) (i * l - k * j) / (l - j);
//					s.insert({ x,y});
//				}
//	cout << s.size() + 41;
//}
//#include<iostream>
//#include<set>
//using namespace std;
//int main()
//{
//    set<pair<double, double> > line;
//    double k, b;
//    for (int x1 = 0; x1 < 20; x1++) {
//        for (int y1 = 0; y1 < 21; y1++) {
//            for (int x2 = x1 + 1; x2 < 20; x2++) {
//                for (int y2 = 0; y2 < 21; y2++) {
//                    if (y2 == y1)continue;
//                    k = (double)(y1 - y2) / (x1 - x2);
//                    b = (double)(x1 * y2 - x2 * y1) / (x1 - x2);
//                    line.insert({ k,b });
//                }
//            }
//        }
//    }
//    cout << line.size() + 41;
//    return 0;
//}
//#include <iostream>
//using namespace std;
//typedef long long LL;
//int main()
//{
//    // ���ڴ��������Ĵ���
//    LL n = 2021041820210418;
//    LL sum = 0;
//    for (LL i = 1; i * i * i <= n; i++)
//    {
//        for (LL j = i; i * j * j <= n; j++)
//        {
//            LL k = n / i / j;
//            if (i * j * k == n)
//            {
//                if (i != j && j != k && k != i)
//                    sum += 6;
//                else if (i == j && i == k)
//                {
//                    sum += 1;
//                }
//                else sum += 3;
//            }
//        }
//    }
//    cout << sum;
//    return 0;
//}
//#include <bits/stdc++.h>
//using namespace std;
//const int N=5e5 + 10;
//typedef long long LL;
//int ne[N], e[N], h[N];
//int idx;
//LL dis[3000];
//LL w[N];
//void add(int a, int b, int c)
//{
//    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
//}
//int gcd(int a, int b)
//{
//    return b ?gcd(b, a % b) : a;
//}
//bool is[3000];
//typedef pair<int, int> PII;
//priority_queue<PII, vector<PII>, greater<PII>>pq;
//void diji(int root)
//{
//    memset(dis, 0x3f, sizeof dis);
//    dis[1] = 0;
//    pq.push({ 0,1 });
//    while (pq.size())
//    {
//        auto it = pq.top();
//        pq.pop();
//        int y = it.second;
//        if (is[y])continue;
//        is[y] = true;
//        if (y == 2020)
//        {
//            cout << "666" << endl;
//        }
//        for (int i = h[y]; ~i ; i = ne[i])
//        {
//            int j = e[i];
//            if (dis[j] > dis[y] + w[i])
//            {
//                dis[j] = dis[y] + w[i];
//                pq.push({ dis[j],j });
//            }
//        }
//    }
//}
//int main()
//{
//    // ���ڴ��������Ĵ���
//    memset(h, -1, sizeof h);
//    for (int i = 1; i <= 2021; i++)
//        for (int j = i + 1; j <= i + 21&&j<=2021; j++)
//        {
//            int x = i * j / gcd(i, j);
//            add(i, j, x);
//            add(j, i, x);
//        }
//    diji(1);
//    cout << dis[2021];
//    return 0;
//}
//#include <iostream>
//using namespace std;
//typedef long long LL;
//LL arr[30];
//int main()
//{
//    // ���ڴ��������Ĵ���
//
//    int t;
//    cin >> t;
//    while (t--)
//    {
//        int sum[30];
//        int n;
//        cin >> n;
//        for (int i = 0; i < n; i++)
//            cin >> arr[i];
//        for (int i = 0; i < 22; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                sum[i] += ((arr[j] >> i) & 1);
//            }
//        }
//        int i;
//        for (i = 20; i >= 0; i--)if (sum[i] % 2)
//        {
//            break;
//        }
//        if (i > -1)cout << 1 << endl;
//        else cout << 0 << endl;
//    }
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//const int N = 1e5 + 10;
//int dis[N];
//int e[N], ne[N], h[N], w[N];
//int idx;
//void add(int a, int b, int c)
//{
//    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
//}
//bool is[N];
//int lujing[N];
//int n, m;
//queue<int>q;
//bool spfa()
//{
//    //    memset(dis, 0x3f, sizeof dis);
//    dis[0] = 0;
//    is[0] = 1;//����Ҫ�ڶ��д��ظ��ĵ�
//    q.push(0);
//    while (q.size())
//    {
//        int pos = q.front();
//        q.pop();
//        is[pos] = 0;
//        for (int i = h[pos]; i != -1; i = ne[i])
//        {
//            int j = e[i];
//            if (dis[j] > dis[pos] + w[i])
//            {
//                dis[j] = dis[pos] + w[i];
//                lujing[j] = lujing[pos] + 1;
//                if (lujing[j] >= n)
//                    return 1;
//                if (0 == is[j])
//                {
//                    is[j] = 1;
//                    q.push(j);
//                }
//            }
//        }
//    }
//    return 0;
//}
//int main()
//{
//    memset(h, -1, sizeof h);
//    cin >> n >> m;
//    for (int i = 0; i < m; i++)
//    {
//        int a, b, c;
//        cin >> a >> b >> c;
//        add(a, b, c);
//    }
//    for (int i = 1; i <= n; i++)
//        add(0, i, -1);
//    if (spfa())
//        cout << "Yes";
//    else
//        cout << "No";
//
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long  LL;
//typedef pair<LL, LL> PLL;
//const int N = 2e5 + 10;
//LL arr[N];
//struct date {
//    int l, r;
//};
//int main() {
//    int t;
//    cin >> t;
//    while (t--) {
//        string s;
//        cin >> s;
//        string ans;
//        int i = 0;
//        while (i < s.size() && s[i] == '0')i++;
//        while (i < s.size())
//        {ans += s[i]; i++;}
//        int x = 0;
//        if (ans.size()) {
//            x = stoi(ans);
//           
//        }
//        int y = sqrt(x);
//        if (y * y == x) {
//            cout << 0 << ' ' << y << endl;
//        }
//        else cout << -1 << endl;
//    }
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long  LL;
//typedef pair<LL, LL> PLL;
//const int N = 2e5 + 10;
//LL arr[N];
//struct date {
//    int l, r;
//};
//int main() {
//    int t;
//    cin >> t;
//    while (t--) {
//        string s;
//        int k, n;
//        cin >> n >> k;
//        cin >> s;
//        int sum0 = 0;
//        for (int i = 0; i < s.size(); i++)if (s[i] == '0')sum0++;
//        int sum1=n - sum0;
//        int Max = sum0/2+sum1/2;
//        int Min = max(sum0, sum1) - min(sum0, sum1);
//        Min /= 2;
//        if (Max>= k&&Min<=k&&((k-Min)%2==0))cout << "YES" << endl;
//        else cout << "NO" << endl;
//    }
//
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long  LL;
//typedef pair<LL, LL> PLL;
//const int N = 2e5 + 10;
//LL arr[N];
//LL brr[N];
//int main() {
//    int t;
//    cin >> t;
//    while (t--) {
//
//        vector<int>v;
//        int n;
//        cin >> n;
//        for (int i = 1; i <= n; i++)cin >> arr[i];
//        int num = 0;
//        int ans = 0;
//        for (int i = 1; i <= n; i++) {
//            if (v.size() == 0)v.push_back(arr[i]);
//            else {
//                if (v[v.size() - 1] > arr[i])
//                {
//                    v.pop_back();
//                    v.push_back(arr[i]);
//                }
//                else if (v[v.size() - 1] + 1 < arr[i])
//                {
//                    v.push_back(arr[i]);
//                }
//            }
//        }
//        cout << v.size() << endl;;
//    }
//
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long  LL;
//typedef pair<LL, LL> PLL;
//const int N = 2e5 + 10;
//PLL arr[N];
//PLL brr[N];
//int main() {
//    int t;
//    cin >> t;
//    while (t--) {
//        int n;
//        cin >> n;
//        for (int i = 1; i <= n; i++) {
//            cin >> arr[i].first >> arr[i].second;
//            brr[i].first = arr[i].second, brr[i].second = arr[i].first;
//        }
//        sort(arr + 1, arr + n + 1);
//        sort(brr + 1, brr + 1 + n);
//        if (n <= 2)cout << n;
//        else {
//            LL zuo1 = arr[1].first;
//            LL x2 = arr[2].first;
//            LL x3 = arr[n - 1].first;
//            LL x4 = arr[n].first;
//           LL y1 = brr[1].first;
//            LL y2 = brr[2].first;
//            LL y3 = brr[n - 1].first;
//            LL y4 = brr[n].first;
//            LL ans=0;
//            ans = (1+y4 - y1) * (1+x4 - x2);
//            ans = min(ans,(y4 - y1+1) * (1+x3 - x1));
//            ans = min(ans, (1+x4 - x1) * (1+y4 - y2));
//            ans = min(ans, (1+x4 - x1) * (1+y3 - y1));
//            cout << ans << endl;
//        }
//
//    }
//
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long  LL;
//struct date {
//    LL a, b;
//    bool operator<(const date d)const {
//        return a < d.a ? 1 : b < d.b;
//    }
//};
//const int N = 2e5 + 10;
//date arr[N];
//int main() {
//    int t;
//    cin >> t;
//    while (t--) {
//        int n;
//        cin >> n;
//        for (int i = 1; i <= n; i++) {
//            cin >> arr[i].a >> arr[i].b;
//        }
//        sort(arr + 1, arr + n + 1);
//        if (n <= 2)cout << n;
//        else {
//            LL x1 = arr[2].a;
//            LL y1 = arr[2].b;
//            LL x2 = arr[n].a;
//            LL y2 = arr[n].b;
//            LL ans = 0;
//            ans = (x2-x1+1)*();
//            ans = min(ans, (y4 - y1 + 1) * (1 + x3 - x1));
//            ans = min(ans, (1 + x4 - x1) * (1 + y4 - y2));
//            ans = min(ans, (1 + x4 - x1) * (1 + y3 - y1));
//            cout << ans << endl;
//        }
//
//    }
//
////}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long  LL;
//typedef pair<LL, LL> PLL;
//const int N = 2e5 + 10;
//
//
//struct date {
//    LL a, b, c;
//    bool operator<(const date d)const {
//        return a < d.a;
//    }
//};
//date arr[N];
//date brr[N];
//date crr[N];
//int main() {
//    int t;
//    cin >> t;
//    while (t--) {
//        int n;
//        cin >> n;
//        for (int i = 1; i <= n; i++) {
//            cin >> arr[i].a >> arr[i].b;
//            arr[i].c = i;
//            brr[i].a = arr[i].b, brr[i].b = arr[i].a;
//            brr[i].c = i;
//            crr[i].a = arr[i].a;
//            crr[i].b = arr[i].b;
//            crr[i].c = i;
//        }
//        sort(crr + 1, crr + n + 1);
//        sort(brr + 1, brr + 1 + n);
//        if (n <= 2)cout << n<<endl;
//        else {
//            LL zuo = crr[1].c;
//            LL you = crr[n].c;
//            LL shang = brr[1].c;
//            LL xia = brr[n].c;
//            LL ans = 0;
//            LL x1 = 0x3f3f3f3f3f;
//            LL x2 = 0;
//            LL y1 = 0x3f3f3f3f3f;
//            LL y2 = 0;
//            LL X = 0, Y = 0;
//            for (int i = 1; i <= n; i++) {
//                if (i == zuo)continue;
//                x1 = min(x1, arr[i].a);
//                x2 = max(x2, arr[i].a);
//                y1 = min(y1, arr[i].b);
//                y2 = max(y2, arr[i].b);
//            }
//            Y = (1 + y2 - y1);
//            X=(1 + x2 - x1);
//            ans = X * Y;
//            if (ans < n)
//            {
//                if (X > Y)swap(X, Y);
//                Y++;
//                ans = X * Y;
//            }
//             x1 = 0x3f3f3f3f3f;
//             x2 = 0;
//             y1 = 0x3f3f3f3f3f;
//             y2 = 0;
//             X = 0, Y = 0;
//            for (int i = 1; i <= n; i++) {
//                if (i == you)continue;
//                x1 = min(x1, arr[i].a);
//                x2 = max(x2, arr[i].a);
//                y1 = min(y1, arr[i].b);
//                y2 = max(y2, arr[i].b);
//            }
//            Y = (1 + y2 - y1);
//            X = (1 + x2 - x1);
//            ans =min(ans, X * Y);
//            if (ans < n)
//            {
//                if (X > Y)swap(X, Y);
//                Y++;
//                ans = X * Y;
//            }
//            x1 = 0x3f3f3f3f3f;
//            x2 = 0;
//            y1 = 0x3f3f3f3f3f;
//            y2 = 0;
//            X = 0, Y = 0;
//            for (int i = 1; i <= n; i++) {
//                if (i == shang)continue;
//                x1 = min(x1, arr[i].a);
//                x2 = max(x2, arr[i].a);
//                y1 = min(y1, arr[i].b);
//                y2 = max(y2, arr[i].b);
//            }
//            Y = (1 + y2 - y1);
//            X = (1 + x2 - x1);
//            ans = min(ans, X * Y);
//            if (ans < n)
//            {
//                if (X > Y)swap(X, Y);
//                Y++;
//                ans = X * Y;
//            }
//            x1 = 0x3f3f3f3f3f;
//            x2 = 0;
//            y1 = 0x3f3f3f3f3f;
//            y2 = 0;
//            X = 0, Y = 0;
//            for (int i = 1; i <= n; i++) {
//                if (i == xia)continue;
//                x1 = min(x1, arr[i].a);
//                x2 = max(x2, arr[i].a);
//                y1 = min(y1, arr[i].b);
//                y2 = max(y2, arr[i].b);
//            }
//            Y = (1 + y2 - y1);
//            X = (1 + x2 - x1);
//            ans = min(ans, X * Y);
//            if (ans < n)
//            {
//                if (X > Y)swap(X, Y);
//                Y++;
//                ans = X * Y;
//            }
//            cout << ans << endl;
//        }
//
//    }
//
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long  LL;
//const int N = 2e5 + 10;
//int e[N * 2], ne[N * 2], h[N];
//int idx;
//void add(int a, int b) {
//    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
//}
//LL arr[N];
//LL Max[N];
//LL Min[N];
//LL cen[N];void dfs(int fa,int u) {
//    for (int i = h[u]; ~i; i = ne[i]) {
//        int j = e[i];
//        if (j == fa)continue;
//        Max[j] = max(arr[j], arr[j] - Min[u]);
//        Min[j] = min(arr[j], arr[j] - Max[u]);
//        dfs(u,j);
//    }
//}
//int main() {
//    int t;
//    cin >> t;
//    while (t--) {
//        memset(h, -1, sizeof(h));
//        int n;
//        cin >> n;
//        for (int i = 1; i <= n; i++)cin >> arr[i];
//        for (int i = 1; i < n; i++) {
//            int x, y;
//            cin >> x >> y;
//            add(x, y);
//            add(y, x);
//        }
//        Max[1] = arr[1];
//        Min[1] = arr[1];
//        dfs(0,1);
//        for (int i = 1; i <= n; i++) {
//            cout << Max[i] << " ";
//        }
//        cout << endl;
//
//    }
//}
// #include<bits/stdc++.h>
// using namespace std;
// vector<long long>v;
// typedef long long LL;
// bool is[1000010];
// void init() {
//     long long n = 1e6;
//     for (long long i = 2; i <= n; i++) {
//         if (is[i] == 0)v.push_back(i);
//         for (long long j = 0;j<v.size()&& v[j] * i <= n; j++) {
//             is[v[j] * i] = true;
//             if (i % v[j] == 0)break;
//         }
//     }
// }
// int main() {
//     init();
//     int n;
//     cin >> n;
//     while (n--) {
//         unordered_map<int, int>mp1;
//         unordered_map<int, int>mp2;

//         LL x, y, k;
//         cin >> x >> y >> k;
//         int Max1 = 0, Max2 = 0;
//         for (int i = 0; i < v.size(); i++) {
//             int num = 0;
//             while (x % v[i] == 0) {
//                 num++;
//                 x /= v[i];
//             }
//             if (num) {
//                 mp1[v[i]] = num;
//                 Max1 = v[i];
//             }
//         }
//         for (int i = 0; i < v.size(); i++) {
//             int num = 0;
//             while (y % v[i] == 0) {
//                 num++;
//                 y /= v[i];
//             }
//             if (num) {
//                 Max2 = v[i];
//                 mp2[v[i]] = num;
//             }
//         }
//         if (Max2> k) {
//             cout << "-1" << endl;
//         }
//         else {
//             vector<int>shan, jian;
//             for (auto i : mp1) {
//                 int x = i.first;
//                 int y = i.second;
//                 if (mp2[x] < y) {
//                     y -= mp2[x];
//                     while (y--)
//                         shan.push_back(x);
//                 }
//             }
//             for (auto i : mp2) {
//                 int x = i.first;
//                 int y = i.second;
//                 if (mp1[x] < y) {
//                     y -= mp1[x];
//                     while (y--)
//                         jian.push_back(x);
//                 }
//             }
//             sort(shan.begin(), shan.end());
//             sort(jian.begin(), jian.end());
//             int ans = 0;
//             for (LL i = 0; i < shan.size();)
//             {
//                 LL j = 1;
//                 while (i<shan.size()&&j * shan[i] <= k)
//                 {
//                     j *= shan[i++];
//                 }
//                 ans++;
//             }
//             for (LL i = 0; i < jian.size();)
//             {
//                 LL j = 1;
//                 while (i<jian.size()&&j * jian[i] <= k)
//                 {
//                     j *= jian[i++];
//                 }
//                 ans++;
//             }
//             cout << ans << endl;
//         }
//     }
// }
// #include<bits/stdc++.h>
// using namespace std;
// typedef long long LL;

// struct date{
//     int a,b;
// }arr[200010];
// int ans[200010];
// void solve(){
//     int n,m;
//     cin>>n>>m;
//     for(int i=1;i<=m;i++){
//         int x,y;
//         cin>>x>>y;
//         x--;
//         while(x>=0){
//             ans[(x+y)%n]++;
//         }
//     }
//     for(int i=0;i<n;i++)cout<<ans[i]<<' ';
//     cout<<endl;
// }
// int main(){
//     int t;
//     cin>>t;
//     while(t--){
//         solve();
//     }
//     return 0;
// }
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long  LL;
//const int N = 2e5 + 10;
//struct date {
//    LL a, pos;
//    bool operator < (const date d)const {
//        return a > d.a;
//    }
//}arr[N];
//LL brr[N];
//bool crr[N];
//int main() {
//    int t;
//    cin >> t;
//    while (t--) {
//        int n;
//        cin >> n;
//        memset(crr, 0, sizeof crr);
//        for (int i = 1; i <= n; i++) {
//            cin >> arr[i].a;
//            arr[i].pos = i;
//            brr[i] = arr[i].a;
//        }
//        sort(arr + 1, arr + 1 + n);
//        LL ans = 0;
//        int j = 1;
//        int last = 0;
//        int k = 0;
//        crr[0] = 1;
//        crr[n + 1] = 1;
//        for (int i = 1; i <= n; i++) {
//            if (crr[k])
//            {
//                cout << "$" << ' ';
//                ans += brr[arr[j].pos];
//                k = arr[j].pos + 1;
//                crr[arr[j].pos] = true;
//                j++;
//            }
//            else {
//                cout << "k" << k << ' ';
//                ans += brr[k];
//                crr[k++] = true;
//            }
//            cout << ans << ' ';
//
//        }
//        cout << endl;
//    }
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long  LL;
//const int N = 2e5 + 10;
//struct date {
//    LL a, pos;
//    bool operator < (const date d)const {
//        return a > d.a;
//    }
//}arr[N];
//LL brr[N];
//bool crr[N];
//int main() {
//    int t;
//    cin >> t;
//    while (t--) {
//        int n;
//        cin >> n;
//        memset(crr, 0, sizeof crr);
//        for (int i = 1; i <= n; i++) {
//            cin >> arr[i].a;
//            arr[i].pos = i;
//            brr[i] = arr[i].a;
//        }
//        sort(arr + 1, arr + 1 + n);
//        LL ans = 0;
//        int j = n;
//        LL left = n+1;
//        int k = 1;
//        for (int i = n; i; i--) {
//            while (k<=n&&crr[arr[k].pos])k++;
//            while (j && crr[j])j--;
//            if (i <= left - 1) {
//               // cout << '#' << ' ';
//                ans += arr[k].a;
//                crr[arr[k].pos] = true;
//                left = min(left, arr[k].pos);
//                k++;
//            }
//            else {
//               // cout << '$' << ' ';
//                ans += brr[j];
//                crr[j] = true;
//                j--;
//            }
//            cout << ans << ' ';
//        }
//        cout << endl;
//    }
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long  LL;
//const int N = 2e5 + 10;
//struct date {
//    LL a, pos;
//    bool operator < (const date d)const {
//        return a > d.a;
//    }
//}arr[N];
//
//int main() {
//    int t;
//    cin >> t;
//    while (t--) {
//        unordered_map<int, int>mp1;
//        unordered_map<int, int>mp2;
//        int n;
//        cin >> n;
//        string s;
//        cin >> s;
//        int num1 = 0, num2 = 0;
//        for (auto i = 0; i < s.size(); i++) {
//            if (s[i] == 'A')
//            {
//                mp1[i + 1] = true;
//            }
//            else {
//                mp2[i + 1] = true;
//            }
//        }
//        if (mp1.count(1) && mp1.count(n))cout << "Alice" << endl;
//        else if (mp2.count(1) && mp2.count(n))cout << "Bob" << endl;
//        else if (mp1.count(1) && n == 2)cout << "Alice" << endl;
//        else if (mp2.count(1) && n == 2)cout << "Bob" << endl;
//        else if (mp1.count(1) && mp2.count(n) && mp2.size() == 1)cout << "Alice" << endl;
//        else if (mp1.count(1) && mp2.count(n) && mp2.size() > 1)cout << "Bob" << endl;
//        else if (mp2.count(1) && mp1.count(n) && mp1.size() == 1)cout << "Bob" << endl;
//        else if (mp2.count(1) && mp1.count(n) && mp1.size() > 1 && mp2.size() == 1)
//            cout << "Alice" << endl;
//        else if (mp1.count(n-1))cout << "Alice" << endl;
//        else cout << "Bob" << endl;
//    }
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long  LL;
//const int N = 2e5 + 10;
//struct date {
//    LL a, pos;
//    bool operator < (const date d)const {
//        return a > d.a;
//    }
//}arr[N];
//int brr[400010];
//int em[400010];
//int num;
//bool is[40000010];
//void init() {
//    for (int i = 2; i <= 40000000 && num <= 400000; i++) {
//        if (is[i] == 0)em[++num] = i;
//        for (int j = 1; em[j] * i <= 40000000; j++) {
//            is[em[j] * i] = true;
//            if (i % em[j] == 0)break;
//        }
//    }
//}
//int main() {
//    int t;
//    cin >> t;
//    init();
//    while (t--) {
//        int n;
//        cin >> n;
//        for (int i = 1; i <= n; i++)cin >> arr[i];
//        sort(arr + 1, arr + 1 + n);
//        LL sum = 0;
//        for (int i = 1; i <= n; i++)sum + arr[i];
//        int i = 1;
//        while (sum < (n - i + 1) * 2) {
//            sum -= arr[i];
//            i++;
//        }
//        LL sum1 = 0;
//        LL sum2 = 0;
//        int j = 1;
//        int ans = 0x3f3f3f3f;
//        for (int i = n; i; i--) {
//            sum2 += em[j];
//            sum1 += arr[n];
//            if (sum1 >= 2 * (n - i + 1) && sum1 >= sum2)
//                ans = (n - j);
//            j++;
//        }
//        cout << ans << endl;
//    }
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long  LL;
//const int N = 2e5 + 10;
//int arr[400010];
//int em[400010];
//int num;
//bool is[40000010];
//void init() {
//    for (int i = 2; i <= 40000000 && num <= 400000; i++) {
//        if (is[i] == 0)em[++num] = i;
//        for (int j = 1; em[j] * i <= 40000000; j++) {
//            is[em[j] * i] = true;
//            if (i % em[j] == 0)break;
//        }
//    }
//}
//int main() {
//    int t;
//    cin >> t;
//    init();
//    while (t--) {
//        int n;
//        cin >> n;
//        for (int i = 1; i <= n; i++)cin >> arr[i];
//        sort(arr + 1, arr + 1 + n);
//        LL sum1 = 0;
//        LL sum2 = 0;
//        int j = 1;
//        int ans = n;
//        for (int i = n; i; i--) {
//            sum2 += em[j];
//            sum1 += arr[i];
//            if (sum1 >= 2 *j && sum1 >= sum2)
//                ans = (n - j);
//            else break;
//            j++;
//        }
//        cout << ans << endl;
//    }
//    return 0;
//}
// #include<bits/stdc++.h>
// using namespace std;
// int arr[1000010][26];
// int dp[1000010];
// int main() {
// 	cin.tie(0);
// 	cout.tie(0);
// 	ios::sync_with_stdio(false);

// 	int n,k;
// 	cin >> n>>k;
// 	string s;
// 	cin >> s;
// 	for (int i = 0; i < s.size(); i++) 
// 		for (int j = 0; j < k; j++)arr[i][j] = s.size();
// 	for (int i = s.size() - 2; i>=0; i--)
// 	{
// 		for (int j = 0; j < k; j++)
// 			arr[i][j] = arr[i + 1][j];
// 		arr[i][s[i + 1] - 'a'] = i + 1;
// 	}
// 	memset(dp, 0x3f, sizeof dp);
// 	dp[s.size()] = 0;
// 	for (int i = s.size() - 1; i>=0; i--) {
// 		for (int j = 0; j < k; j++)
// 			dp[i] = min(dp[arr[i][j]]+1, dp[i]);
// 	}
// 	int q;
// 	cin >> q;
// 	while (q--) {
// 		string s1;
// 		cin >> s1;
// 		int pos = arr[0][s1[0] - 'a'];
// 		if (s1[0] == s[0])pos = 0;
// 		if (pos == s.size()) {
// 			cout << "0" << endl; continue;
// 		}
// 		int j = 1;
// 		for (; j < s1.size(); j++)
// 		{
// 			pos = arr[pos][s1[j] - 'a'];
// 			if (pos == s.size())break;
// 		}
// 		if (j == s1.size()) {
// 			cout << dp[pos] << endl;
// 		}
// 		else cout << 0 << endl;
// 	}
// }
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long  LL;
//const int N = 1e5 + 10;
////LL arr[N];
////LL brr[N];
//struct date{
//	LL a,pos;
//	bool operator < (const date d)const {
//		return a > d.a;
//	}
//}arr[N],brr[N];
//LL ans[N];
//LL MOD=998244353;
//LL f(LL x){
//    LL ans=1;
//    LL a=2;
//    while(x){
//        if(x&1)ans=ans*a%MOD;
//        a=a*a%MOD;
//        x>>=1;
//    }
//    return ans%MOD;
//}
//int main(){
//	int t;
//	cin>>t;
//	while(t--){
//		int n;
//        cin>>n;
//        for(int i=0;i<n;i++)cin>>arr[i];
//        for(int i=0;i<n;i++){
//			cin>>brr[i];
//			crr[i].a=brr[i];
//			crr[i].pos=i;
//		}
//		sort(crr,crr+n);
//	
//
//        for(int i=1;i<=n;i++)arr[i]=f(arr[i]);
//        for(int i=1;i<=n;i++)brr[i]=f(brr[i]);
//     	for(int i=0;i<n;i++){
//			int pos=crr[i].pos;
//			ans[pos]=(arr[0]+brr[pos])%MOD;
//		}
//		for(int i=0;i<n;i++)
//		cout<<ans[i]%MOD<<' ';
//		cout<<endl;
//	}
//	return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long  LL;
//const int N = 1e5 + 10;
//struct date {
//	LL a, pos;
//	bool operator < (const date d)const {
//		return a < d.a;
//	}
//}arr[N], brr[N];
//LL Arr[N], Brr[N];
//LL ans[N];
//LL MOD = 998244353;
//LL f(LL x) {
//	LL ans = 1;
//	LL a = 2;
//	while (x) {
//		if (x & 1)ans = ans * a % MOD;
//		a = a * a % MOD;
//		x >>= 1;
//	}
//	return ans % MOD;
//}
//int main() {
//	int t;
//	cin >> t;
//	while (t--) {
//		int n;
//		cin >> n;
//		for (int i = 0; i < n; i++) {
//			cin >> arr[i].a; arr[i].pos = i;
//			Arr[i] = arr[i].a;
//		}
//		for (int i = 0; i < n; i++) {
//			cin >> brr[i].a;
//			Brr[i] = brr[i].a;
//			brr[i].pos = i;
//		}
//
//
//		sort(arr, arr + n);
//		sort(brr, brr + n);
//		int j = 0;
//		int pos = 0;
//		for (int i = 0; i < n; i++)Arr[i] = f(Arr[i]);
//		for (int i = 0; i < n; i++)Brr[i]= f(Brr[i]);
//		for (int i = 0; i < n; i++) {
//			if(j<)
//		}
//		for (int i = 0; i < n; i++)
//			cout << ans[i] % MOD << ' ';
//		cout << endl;
//	}
//	return 0;
//}
//
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long  LL;
//const int N = 1e5 + 10;
//LL arr[N], brr[N];
//LL Arr[N], Brr[N];
//LL MOD = 998244353;
//LL crr[N];
//int main() {
//	int t;
//	cin >> t;
//	crr[0] = 1;
//	for (int i = 1; i < N; i++)
//		crr[i] = crr[i - 1] * 2 % MOD;
//	while (t--) {
//		LL n;
//		cin >> n;
//		for (LL i = 0; i < n; i++) {
//			cin >> arr[i];
//		}
//		for (LL i = 0; i < n; i++) {
//			cin >> brr[i];
//		}
//		for (int i = 0; i < n; i++)
//			if (arr[i] >= arr[Arr[i - 1]])Arr[i] = i;
//			else Arr[i] = Arr[i - 1];
//		for (int i = 0; i < n; i++)
//			if (brr[i] >= brr[Brr[i - 1]])Brr[i] = i;
//			else Brr[i] = Brr[i - 1];
//
//		for (int i = 0; i < n; i++) {
//			LL ans = 0;
//			if (arr[Arr[i]] > brr[Brr[i]])
//				cout << (crr[arr[Arr[i]]] + crr[brr[i - Arr[i]]]) % MOD << ' ';
//			else if (Arr[arr[i]] < Brr[brr[i]])
//				cout << (crr[brr[Brr[i]]] + crr[arr[i - Brr[i]]]) % MOD << ' ';
//			else {
//				if (arr[i - Brr[i]] > brr[i - Arr[i]])
//					cout << (crr[arr[i - Brr[i]]] + crr[brr[Brr[i]]]) % MOD << ' ';
//				else cout << (crr[brr[i - Arr[i]]] + crr[arr[Arr[i]]]) % MOD << ' ';
//			}
//		}
//		cout << endl;
//	}
//	return 0;
//}

//#include <bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//const LL maxN = 1e5 + 5, delta = 998244353;
//LL t, n, p[maxN], q[maxN], two[maxN];
//LL P[maxN], Q[maxN];
//LL f(LL x) {
//	LL ans = 1;
//	LL a = 2;
//	while (x) {
//		if (x & 1)ans = ans * a % delta;
//		a = a * a % delta;
//		x >>= 1;
//	}
//	return ans;
//}
//void solve() {
//	cin >> n;
//	for (int i = 0; i < n; i++) {
//		cin >> p[i]; P[i] = p[i];
//	}
//	for (int i = 0; i < n; i++) {
//		cin >> q[i];
//		Q[i] = q[i];
//	}
//	for (int i = 0; i <n ; i++) {
//		P[i] = f(P[i]);
//		Q[i] = f(Q[i]);
//	}
//	LL Max1 = -1, Max2 = -1;
//	LL pmaxi = 0, qmaxi = 0;
//	for (int i = 0; i < n; i++) {
//		if (Max1 < p[i]) pmaxi = i, Max1 = p[i];
//		if (Max2 < q[i]) qmaxi = i, Max2 = q[i];
//		if (Max1 > Max2) 
//			cout << (P[pmaxi] + Q[i - pmaxi]) % delta << ' ';
//		else if (Max1 < Max2) 
//			cout << (P[i - qmaxi] + Q[qmaxi]) % delta << ' ';
//		else 
//			if (p[i - qmaxi] > q[i - pmaxi])
//				cout << (P[i - qmaxi] + Q[qmaxi]) %delta<< ' ';
//			else cout << (Q[i - pmaxi] + P[pmaxi])%delta << ' ';
//	}
//	cout << '\n';
//}
//
//int main() {
//	two[0] = 1;
//	for (int i = 1; i <= 1e5; i++)
//		two[i] = (two[i - 1] << 1) % delta;
//	cin >> t;
//	while (t--)solve();
//	cout << f(10000);
//}
//#include<bits/stdc++.h>
//using namespace std;
//const int N = 2010;
//typedef long long LL;
//LL e[N], ne[N], w[N], su[N], h[N];
//int idx;
//void add(int a, int b, LL c, LL d) {
//    e[idx] = b, ne[idx] = h[a], h[a] = idx, su[idx] = d, w[idx++] = c;
//}
//LL dp1[2000];//总费用
//LL dp2[2000];//速度
//int main() {
//    int n, m;
//    cin >> n >> m;
//    memset(h, -1, sizeof h);
//    for (int i = 1; i <= m; i++) {
//        int a, b, c, d;
//        cin >> a >> b >> c >> d;
//        add(a, b, c, d * 1000000);
//        add(b, a, c, d * 1000000);
//    }
//    memset(dp1, 0x3f, sizeof dp1);
//    memset(dp2, 1, sizeof dp2);
//    queue<int>q;
//    q.push(1);
//    dp1[1] = 0;
//    dp2[1] = 0x3f3f3f3f;
//    while (q.size()) {
//        int k = q.front();
//        //std::cout<<k<<' '<<dp1[k]<<' '<<dp2[k]<<endl;
//        q.pop();
//        for (int i = h[k]; i != -1; i = ne[i]) {
//            int j = e[i];
//            // cout<<j<<' ';
//            if (dp1[k] == 0 || (min(dp2[k], su[i]) / (dp1[k] + w[i]) > dp2[j] / dp1[j])) {
//                q.push(j);
//                dp1[j] = dp1[k] + w[i];
//                dp2[j] = min(dp2[k], su[i]);
//            }
//
//        }
//    }
//    cout << dp2[n] / (dp1[n]);
//    return 0;
//}
//#include<iostream>
//#include<queue>
//#include<cstring>
//#include<vector>
//#include<map>
//#include<algorithm>
//#include<cmath>
//
//using namespace std;
//typedef long long LL;
//const int N = 2e5 + 10;
//LL arr[N];
//int main() {
//    int t;
//    cin >> t;
//    for (int i = 0; i < t; i++) {
//        LL x;
//        cin >> x;
//        LL a = 0;
//        LL sum = 0;
//        while (a < x) {
//            sum += 2;
//            a = a * 2 + 1;
//        }
//        sum++;
//        cout << sum << endl;
//    }
//    return 0;
//}
//#include<iostream>
//#include<queue>
//#include<cstring>
//#include<vector>
//#include<map>
//#include<algorithm>
//#include<cmath>
//
//using namespace std;
//typedef long long LL;
//const int N = 5e5 + 10;
//map<LL, LL>mp;
//LL arr[N];
//int main() {
//    int t;
//    cin >> t;
//    while (t--) {
//        mp.clear();
//        LL n;
//        cin >> n;
//        for (int i = 1; i <= n; i++)cin >> arr[i];
//        LL num = 1;
//        for (int i = 1; i < n; i++) {
//            if (arr[i] == arr[i + 1]) {
//                num++;
//            }
//            else {
//                mp[arr[i]] = max(mp[arr[i]], num);
//                num = 1;
//            }
//        }
//        LL ans = 1e17+10;
//        mp[arr[n]] = max(mp[arr[n]], num);
//        for (auto i : mp) {
//            LL a = i.first;
//            LL b = i.second;
//            ans = min(ans, (n - b) * a);
//        }
//        cout << ans << endl;
//    }
//    return 0;
//}
//#include<iostream>
//#include<queue>
//#include<cstring>
//#include<vector>
//#include<map>
//#include<algorithm>
//#include<cmath>
//
//using namespace std;
//typedef long long LL;
//const int N = 2e5 + 10;
//LL arr[N];
//struct date {
//    LL a, b, c;
//    bool operator<(const date d)const {
//        int ma = max({ a,b,c });
//        int mb = max({ d.a,d.b,d.c });
//        return ma > mb;
//    }
//} brr[N];
//int main() {
//    int t;
//    cin >> t;
//    int arr[11] = { 0 };
//    arr[1] = 1, arr[2] = 2;
//    for (int i = 3; i <= 10; i++)arr[i] = arr[i - 1] + arr[i - 2];
//
//    while (t--) {
//        LL n, m;
//        cin >> n >> m;
//        for (int i = 0; i < m; i++) {
//
//            LL w, l, h;
//            cin >> w >> l >> h;
//            int flag = 1;
//           
//            LL k = max({ w,l,h });
//            LL kk = min({ w,l,h });
//            if (k >= arr[n] + arr[n - 1]&&kk>=arr[n])cout << 1;
//            else cout << 0;
//        }
//        cout << endl;
//    }
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//LL arr[100010];
//int main()
//{
//int t;
//cin >> t;
//while (t--) {
//    int n,m;
//    cin >> n >> m;
//    for (int i = 1; i <= m; i++)cin >> arr[i];
//    sort(arr + 1,arr + 1 + m);
//    int j = 1;
//    for (int i = 1; i <= n; i++) {
//        for (int k = 1; k <= 3; k++)
//        cout << arr[j] << ' ' << arr[m - j + 1] << ' ';
//        cout << endl;
//        if (i % 2 == 0)j++;
//    }
//}
//}
//#include<bits/stdc++.h>
//using namespace std;
//int arr[200010];
//int brr[200010];
//int crr[200010];
//int main() {
//    int t;
//    cin >> t;
//    while (t--) {
//        int n, m;
//        cin >> n >> m;
//        string s;
//        cin >> s;
//        s = s;
//        int posa = -1, posb = -1, posc = -1;
//        for (int i = n - 1; i >= 0; i--) {
//            if (s[i] == 'a') {
//                arr[i] = posa;
//                posa = i;
//            }
//            if (s[i] == 'b') {
//                brr[i] = posb;
//                posb = i;
//            }
//            if (s[i] == 'c') {
//                crr[i] = posc;
//                posc = i;
//            }
//        }
//        string ans = s;
//        for (int i = 1; i <= m; i++) {
//            char a, b;
//            cin >> a >> b;
//            if (a == b);
//            else if (a > b) {
//                if (a == 'a')
//                {
//                    int posaa = posa;
//                    if (posa != -1) {
//                        posa = arr[posa];
//                        s[posaa] = b;
//                        if (b == 'a') {
//                            arr[posaa] = posa;
//                            posa = posaa;
//                        }
//                        else if (b == 'b') {
//                            brr[posaa] = posb;
//                            posb = posaa;
//                        }
//                        else {
//                            crr[posaa] = posc;
//                            posc = posaa;
//                        }
//                    }
//                }
//                else if (a == 'b') {
//                    int posaa = posb;
//                    if (posb != -1) {
//                        posb = brr[posb];
//                        s[posaa] = b;
//                        if (b == 'a') {
//                            arr[posaa] = posa;
//                            posa = posaa;
//                        }
//                        else if (b == 'b') {
//                            brr[posaa] = posb;
//                            posb = posaa;
//                        }
//                        else {
//                            crr[posaa] = posc;
//                            posc = posaa;
//                        }
//                    }
//                }
//                else {
//                    int posaa = posc;
//                    if (posc != -1) {
//                        posc = crr[posc];
//                        s[posaa] = b;
//                        if (b == 'a') {
//                            arr[posaa] = posa;
//                            posa = posaa;
//                        }
//                        else if (b == 'b') {
//                            brr[posaa] = posb;
//                            posb = posaa;
//                        }
//                        else {
//                            crr[posaa] = posc;
//                            posc = posaa;
//                        }
//                    }
//                }
//            }
//            else {
//                if (ans > s)ans = s;
//                if (a == 'a');
//                else {
//                    crr[posb] = posc;
//                    posc = posb;
//                }
//            }
//        }
//        cout << s << endl;
//    }
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//int arr[510000];
//int main() {
//    int n, m;
//    cin >> n >> m;
//    int l = 1, r = 1;
//    int ans = -0x3f3f3f3f;
//    int sum = 0;
//    for (int i = 1; i <= n; i++)cin >> arr[i];
//    for (int r = 1; r <= n; r++) {
//        sum += arr[r];
//        while (r - l + 1 > m)sum -= arr[l++];
//        ans = max(ans, sum);
////        if (sum < 0) {
////            sum = 0;
////            l = r + 1;
////        }
////    }
////    while (l < n) {
////        sum -= arr[l++];
////        ans = max(ans, sum);
////    }
////    cout << ans;
////    return 0;
////}
//#include <iostream>
//#include <deque>
//using namespace std;
//const int N = 5e5 + 10;
//int n, m;
//int f[N];
//int main()
//{
//	cin >> n >> m;
//		for (int i = 1; i <= n; i++)
//		{
//			int x; cin >> x;
//			f[i] = f[i - 1] + x;
//		}
//	int ret = -500;
//	deque<int> q;
//	q.push_back(0);
//	for (int i = 1; i <= n; i++)
//	{
//		ret = max(ret, f[i] - f[q.front()]);
//		if(ret==)
//		while (q.size() && f[q.back()] >= f[i]) q.pop_back();
//		q.push_back(i);
//		if (q.back() - q.front() + 1 > m) q.pop_front();
//	}
//	cout << ret << endl;
//	return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef __int128 LL;
//LL n, m;
//LL read() {
//    LL ans = 0;
//    char c = getchar();
//    while (c < '0' || c>'9')c = getchar();
//    while (c >= '0' && c <= '9') {
//        ans = ans * 10 + c - '0';
//        c = getchar();
//    }
//    return ans;
//}
//void print(LL x) {
//    if (x > 9)print(x / 10);
//    putchar(x % 10 + '0');
//}
//LL arr[100];
//LL er[100];
//void init() {
//    er[0] = 1;
//    for (int i = 1; i <= 80; i++)er[i] = er[i - 1] * 2;
//}
//LL dp[100][100];
//LL ans;
//void solve() {
//    for (int i = 1; i <= m; i++)dp[i][i] = arr[i] * er[1];
//    for (int len = 2; len <= m; len++)
//        for (int j = 1; j + len - 1 <= m; j++) {
//            int r = j + len - 1;
//            dp[j][r] = max(dp[j][r - 1] *2+arr[r]*2, dp[j + 1][r]*2 + arr[j]*2);
//        }
//    ans += dp[1][m];
//}
//int main() {
//    n = read();
//    m = read();
//    init();
//    for (int i = 1; i <= n; i++) {
//        for (int i = 1; i <= m; i++)arr[i] = read();
//        solve();
//    }
//    print(ans);
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//LL p, q, a1, a2, n, m;
//
//struct date {
//    LL arr[3][3];
//    date() {
//        memset(arr, 0, sizeof arr);
//    }
//    date operator*(const date d)const {
//        date temp;
//        for (int i = 1; i <= 2; i++)
//            for (int j = 1; j <= 2; j++)
//                for (int k = 1; k <= 2; k++) {
//                    temp.arr[i][j] += arr[i][k] * d.arr[k][j];
//                }
//        return temp;
//    }
//};
//void qmi(date a, int b, date c) {
//    while (b) {
//        if (b & 1)c = c * a;
//        b >>= 1;
//        a = a * a;
//    }
//    cout << c.arr[1][1]%m;
//}
//int main() {
//    cin >> p >> q >> a1 >> a2 >> n >> m;
//    date a, b;
//    a.arr[1][1] = p;
//    a.arr[1][2] = q;
//    a.arr[2][1] = 1;
//    a.arr[2][2] = 0;
//    b.arr[1][1] = a2;
//    b.arr[2][1] = a1;
//    if (n == 1)cout << a1 % m;
//    else if (n == 2)cout << a2 % m;
//    else {
//        qmi(a, n - 2, b);
//    }
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//const int N = 1e5;
//int cnt[100100];
//LL arr[10000010];
//LL read() {
//    LL ret = 0;
//    char c = getchar();
//    while (c < '0' || c>'9')c = getchar();
//    while (c >= '0' || c <= '9') {
//        ret = ret * 10 + c - '0';
//        c = getchar();
//    }
//    return ret;
//}
//int main() {
//    int n;
//    n = read();
//    for (int i = 1; i <= n; i++) {
//        int x;
//        cnt[x = read()]++;
//    }
//    LL sum = 0;
//    int hh = 0, tt = -1;
//    for (int i = 1; i <= N || hh != tt;) {
//        while (i <= N && cnt[i] == 0)i++;
//        if (i > N && hh == tt)break;
//        LL x1 = 1e18;
//        if (i <= N)
//            x1 = i;
//        LL x2 = 1e18;
//        if (hh <= tt) {
//            x2 = arr[hh];
//        }
//        if (x1 < x2) {
//            cnt[i]--;
//            while (i <= N && cnt[i] == 0)i++;
//        }
//        else hh++;
//        x1 = min(x1, x2);
//        LL y1 = 1e18;
//        if (i <= N)y1 = i;
//        LL y2 = 1e18;
//        if (hh <= tt)
//            y2 = arr[hh];
//        if (y1 < y2)cnt[i]--;
//        else hh++;
//        y1 = min(y1, y2);
//        sum += y1 + x1;
//        arr[++tt] = y1 + x1;
//    }
//    cout << sum;
//    return 0;
//}
//#include<bits/stdc++.h>
//using namespace std;
//int n, m;
//bool is[510][510];
//int l[510][510];
//int r[510][510];
//int arr[510][510];
//int xrr[4] = { 0,0,1,-1 };
//int yrr[4] = { -1,1,0,0 };
//void dfs(int i, int j) {
//	if (is[i][j])return;
//	is[i][j] = 1;
//	for (int k = 0; k< 4; k++) {
//		int x = i + xrr[k];
//		int y = j + yrr[k];
//		if (x == 0 || y == 0 || x > n || y > m || arr[x][y] >= arr[i][j])continue;
//		dfs(x, y);
//		l[i][j] = min(l[i][j], l[x][y]);
//		r[i][j] = max(r[i][j], r[x][y]);
//	}
//}
//int main() {
//	cin >> n >> m;
//	memset(l, 0x3f3f3f3f, sizeof l);
//	for (int i = 1; i <= m; i++)l[n][i] =r[n][i]= i;
//	for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> arr[i][j];
//		for (int i = 1; i <= m; i++) {
//			dfs(1, i);
//		}
//		int k = 0;
//		for (int i = 1; i <= m; i++) 
//			k += (is[n][i] == 0);
//		if (k) {
//			cout << 0 << endl;
//			cout << k << endl;
//		}
//		else {
//			int rr = 1;
//			int cnt = 0;
//			while (rr < m) {
//				int Max = 0;
//				for (int i = 1; i <= m; i++) {
//					if (l[1][i] <= rr)Max = max(Max, r[1][i]);
//				}
//				rr = Max;
//				cnt++;
//			}
//			cout << 1 << endl;
//			cout << cnt << endl;
//		}
//}
//#include<bits/stdc++.h>
//using namespace std;
//typedef __int128 LL;
//LL read() {
//    LL ret = 0;
//    char c = getchar();
//    while (c < '0' || c>'9')c = getchar();
//    while (c >= '0' || c <= '9') {
//        ret = ret * 10 + c - '0';
//        c = getchar();
//    }
//    return ret;
//}
//int main() {
//    int n;
//    cin >> n;
//    while (n--) {
//        LL n = read();
//        LL m = read();
//        LL k = (m + n) * (m - n + 1) / 2;
//        int ans = k % 9;
//        cout << ans << endl;
//    }
//    return 0;
//}
#include<bits/stdc++.h>
using namespace std;
set<int>p[2];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >>x ; p[x].insert(i);
    }
    while (p[0].size() || p[1].size()) {
        int st = 0;
        if (p[1].empty() || (p[0].size()&&*p[0].begin() < *p[1].begin()))st = 0;
        else st = 1;
        int x = 0;
        while (1) {
            auto k = p[st].upper_bound(x);
            if (k == p[st].end())break;
            cout << *k << ' ';
            x = *k;
            p[st].erase(k);
            st = !st;
        }
        cout << endl;
    }
}